Add Telephony satellite on-device access control module and tools
Bug: 313773568
Test: atest SatelliteToolsTests TeleServiceTests
Change-Id: I096310b71ec92beffed42321ed4205ac085dcf8c
diff --git a/utils/satellite/README.md b/utils/satellite/README.md
new file mode 100644
index 0000000..e219823
--- /dev/null
+++ b/utils/satellite/README.md
@@ -0,0 +1,62 @@
+This directory contains code and tools for generating and debugging binary
+satellite s2 file.
+
+Directory structure
+=
+
+`s2storage`
+- `src/write` S2 write code used by tools to write the s2 cells into a
+ binary file. This code is also used by `TeleServiceTests`.
+- `src/readonly` S2 read-only code used by the above read-write code and the class
+ `S2RangeFileBasedSatelliteLocationLookup`.
+
+`tools`
+- `src/main` Contains the tools for generating binary satellite s2 file, and tools
+ for dumping the binary file into human-readable format.
+- `src/test` Contains the test code for the tools.
+
+Run unit tests
+=
+- Build the tools and test code: Go to the tool directory (`packages/services/Telephony/tools/
+ satellite`) in the local workspace and run `mm`, e.g.,
+- Run unit tests: `$atest SatelliteToolsTests`
+
+Data file generate tools
+=
+
+`satellite_createsats2file`
+- Runs the `satellite_createsats2file` to create a binary satellite S2 file from a
+ list of S2 cells ID.
+- Command: `$satellite_createsats2file --input-file <s2cells.txt> --s2-level <12>
+ --is-allowed-list <true> --output-file <sats2.dat>`
+ - `--input-file` Each line in the file contains a `signed-64bit` number which represents
+ the ID of a S2 cell.
+ - `--s2-level` The S2 level of all the cells in the input file.
+ - `--is-allowed-list` Should be either `trrue` or `false`
+ - `true` The input file contains a list of S2 cells where satellite services are allowed.
+ - `false` The input file contains a list of S2 cells where satellite services are disallowed.
+ - `--output-file` The created binary satellite S2 file, which will be used by
+ the `SatelliteAccessController` module in determining if satellite communication
+ is allowed at a location.
+- Build the tools: Go to the tool directory (`packages/services/Telephony/tools/satellite`)
+ in the local workspace and run `mm`.
+- Example run command: `$satellite_createsats2file --input-file s2cells.txt --s2-level 12
+ --is-allowed-list true --output-file sats2.dat`
+
+Debug tools
+=
+
+`satellite_createsats2file_test`
+- Create a test binary satellite S2 file with the following ranges:
+ - [(prefix=0b100_11111111, suffix=1000), (prefix=0b100_11111111, suffix=2000))
+ - [(prefix=0b100_11111111, suffix=2000), (prefix=0b100_11111111, suffix=3000))
+ - [(prefix=0b101_11111111, suffix=1000), (prefix=0b101_11111111, suffix=2000))
+- Run the test tool: `$satellite_createtestsats2file /tmp/foo.dat`
+ - This command will generate the binary satellite S2 cell file `/tmp/foo.dat` with
+ the above S2 ranges.
+
+`satellite_dumpsats2file`
+- Dump the input binary satellite S2 cell file into human-readable text format.
+- Run the tool: `$satellite_dumpsats2file /tmp/foo.dat /tmp/foo`
+ - `/tmp/foo.dat` Input binary satellite S2 cell file.
+ - `/tmp/foo` Output directory which contains the output text files.
\ No newline at end of file
diff --git a/utils/satellite/s2storage/Android.bp b/utils/satellite/s2storage/Android.bp
new file mode 100644
index 0000000..64882ee
--- /dev/null
+++ b/utils/satellite/s2storage/Android.bp
@@ -0,0 +1,77 @@
+// Copyright (C) 2020 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Library for read-only access to Sat S2 data files.
+package {
+ default_applicable_licenses: ["Android-Apache-2.0"],
+}
+
+// Library for read-only access to satellite S2 data files.
+java_library {
+ name: "satellite-s2storage-ro",
+ host_supported: true,
+ srcs: [
+ "src/readonly/java/**/*.java",
+ ],
+ static_libs: [
+ "s2storage_ro",
+ ],
+}
+
+// Library for read/write access to satellite S2 data files.
+// This can be a java_library_host since it is used by satellite tools, which runs on host. However,
+// it is also used by the unit test S2RangeFileBasedSatelliteLocationLookupTest, which runs on
+// device. Thus, we need to make it a java_library to support the device-side usage,
+// `host_supported: true` to support the host-side usage.
+java_library {
+ name: "satellite-s2storage-rw",
+ host_supported: true,
+ srcs: [
+ "src/write/java/**/*.java",
+ ],
+ static_libs: [
+ "satellite-s2storage-ro",
+ "s2storage_rw",
+ ],
+}
+
+// Library for access to satellite S2 utils.
+java_library {
+ name: "satellite-s2storage-testutils",
+ host_supported: true,
+ srcs: [
+ "src/testutils/java/**/*.java",
+ ],
+ static_libs: [
+ "junit",
+ "satellite-s2storage-ro",
+ ],
+}
+
+// Tests for the satellite S2 storage code.
+java_test_host {
+ name: "SatelliteS2StorageTests",
+ srcs: ["src/test/java/**/*.java"],
+ static_libs: [
+ "junit",
+ "mockito",
+ "objenesis",
+ "satellite-s2storage-rw",
+ "satellite-s2storage-testutils",
+ ],
+ test_options: {
+ unit_test: true,
+ },
+ test_suites: ["general-tests"],
+}
\ No newline at end of file
diff --git a/utils/satellite/s2storage/TEST_MAPPING b/utils/satellite/s2storage/TEST_MAPPING
new file mode 100644
index 0000000..7d0fba8
--- /dev/null
+++ b/utils/satellite/s2storage/TEST_MAPPING
@@ -0,0 +1,7 @@
+{
+ "postsubmit": [
+ {
+ "name": "SatelliteS2StorageTests"
+ }
+ ]
+}
\ No newline at end of file
diff --git a/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/HeaderBlock.java b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/HeaderBlock.java
new file mode 100644
index 0000000..9895d1a
--- /dev/null
+++ b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/HeaderBlock.java
@@ -0,0 +1,78 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range.read;
+
+import com.android.storage.block.read.BlockData;
+import com.android.storage.util.Visitor;
+
+/**
+ * Wraps a {@link BlockData}, interpreting it as a satellite S2 data file header (block 0). This
+ * class provides typed access to the information held in the header for use when reading a
+ * satellite S2 data file.
+ */
+public final class HeaderBlock {
+ /** Used for converting from bool type to int type */
+ public static final int TRUE = 1;
+ public static final int FALSE = 0;
+
+ private final SatS2RangeFileFormat mFileFormat;
+
+ private HeaderBlock(BlockData blockData) {
+ int offset = 0;
+
+ // Read the format information.
+ int dataS2Level = blockData.getUnsignedByte(offset++);
+ int prefixBitCount = blockData.getUnsignedByte(offset++);
+ int suffixBitCount = blockData.getUnsignedByte(offset++);
+ int suffixRecordBitCount = blockData.getUnsignedByte(offset++);
+ int suffixTableBlockIdOffset = blockData.getUnsignedByte(offset++);
+ boolean isAllowedList = (blockData.getUnsignedByte(offset) == TRUE);
+ mFileFormat = new SatS2RangeFileFormat(
+ dataS2Level, prefixBitCount, suffixBitCount, suffixTableBlockIdOffset,
+ suffixRecordBitCount, isAllowedList);
+ }
+
+ /** Creates a {@link HeaderBlock} from low-level block data from a block file. */
+ public static HeaderBlock wrap(BlockData blockData) {
+ return new HeaderBlock(blockData);
+ }
+
+ /** Returns the {@link SatS2RangeFileFormat} for the file. */
+ public SatS2RangeFileFormat getFileFormat() {
+ return mFileFormat;
+ }
+
+ /** A {@link Visitor} for the {@link HeaderBlock}. See {@link #visit} */
+ public interface HeaderBlockVisitor extends Visitor {
+
+ /** Called after {@link #begin()}, once. */
+ void visitFileFormat(SatS2RangeFileFormat fileFormat);
+ }
+
+ /**
+ * Issues callbacks to the supplied {@link HeaderBlockVisitor} containing information from the
+ * header block.
+ */
+ public void visit(HeaderBlockVisitor visitor) throws Visitor.VisitException {
+ try {
+ visitor.begin();
+ visitor.visitFileFormat(mFileFormat);
+ } finally {
+ visitor.end();
+ }
+ }
+}
diff --git a/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/PopulatedSuffixTableBlock.java b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/PopulatedSuffixTableBlock.java
new file mode 100644
index 0000000..9aa56b2
--- /dev/null
+++ b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/PopulatedSuffixTableBlock.java
@@ -0,0 +1,222 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range.read;
+
+import static com.android.storage.s2.S2Support.MAX_FACE_ID;
+import static com.android.storage.s2.S2Support.cellIdToString;
+import static com.android.storage.util.Conditions.checkStateInRange;
+
+import com.android.storage.s2.S2LevelRange;
+import com.android.storage.table.packed.read.IntValueTypedPackedTable;
+import com.android.storage.table.reader.IntValueTable;
+
+import java.util.Objects;
+
+/**
+ * An implementation of {@link SuffixTableBlock.SuffixTableBlockDelegate} for tables that are backed
+ * by real block data, i.e. have one or more entries.
+ *
+ * <p>Logically, each populated suffix table block holds one or more entries for S2 ranges, e.g.:
+ * <pre>
+ * startCellId=X, endCellId=Y
+ * </pre>
+ *
+ * <p>The storage of the range entries is as follows:
+ * <ul>
+ * <li>The prefix bits are all the same so need not be stored in the individual entries. Only
+ * the suffix bits of X are stored. The prefix determines the block ID when first locating the
+ * suffix table, but it is also (redundantly) stored in the table's header for simplicity /
+ * easy debugging.</li>
+ * <li>Each range is expected to be relatively short, so Y is stored as a offset adjustment to
+ * X, i.e. Y is calculated by advancing X by {length of range} cell IDs.</li>
+ * </ul>
+ */
+final class PopulatedSuffixTableBlock implements SuffixTableBlock.SuffixTableBlockDelegate {
+
+ private final SatS2RangeFileFormat mFileFormat;
+
+ private final IntValueTypedPackedTable mPackedTable;
+
+ private final SuffixTableSharedData mSuffixTableSharedData;
+
+ private final int mPrefix;
+
+ PopulatedSuffixTableBlock(
+ SatS2RangeFileFormat fileFormat, IntValueTypedPackedTable packedTable) {
+ mFileFormat = Objects.requireNonNull(fileFormat);
+ mPackedTable = Objects.requireNonNull(packedTable);
+ mSuffixTableSharedData = SuffixTableSharedData.fromBytes(packedTable.getSharedData());
+
+ // Obtain the prefix. All cellIds in this table will share the same prefix except for end
+ // range values (which are exclusive so can be for mPrefix + 1 with a suffix value of 0).
+ mPrefix = mSuffixTableSharedData.getTablePrefix();
+ }
+
+ @Override
+ public int getPrefix() {
+ return mPrefix;
+ }
+
+ @Override
+ public SuffixTableBlock.Entry findEntryByCellId(long cellId) {
+ int suffixValue = mFileFormat.extractSuffixValueFromCellId(cellId);
+ S2CellMatcher matcher = new S2CellMatcher(mFileFormat, suffixValue);
+ return findEntryWithMatcher(matcher);
+ }
+
+ @Override
+ public SuffixTableBlock.Entry findEntryByIndex(int i) {
+ return new Entry(mPackedTable.getEntryByIndex(i));
+ }
+
+ @Override
+ public int getEntryCount() {
+ return mPackedTable.getEntryCount();
+ }
+
+ /**
+ * Returns an entry that matches the supplied matcher. If multiple entries match, an arbitrary
+ * matching entry is returned. If no entries match then {@code null} is returned.
+ */
+ private SuffixTableBlock.Entry findEntryWithMatcher(
+ IntValueTable.IntValueEntryMatcher matcher) {
+ IntValueTable.TableEntry suffixTableEntry = mPackedTable.findEntry(matcher);
+ if (suffixTableEntry == null) {
+ return null;
+ }
+ return new Entry(suffixTableEntry);
+ }
+
+ /**
+ * An {@link IntValueTable.IntValueEntryMatcher} capable of interpreting and matching the
+ * key/value from the underlying table against a search suffix value.
+ */
+ private static final class S2CellMatcher implements IntValueTable.IntValueEntryMatcher {
+
+ private final SatS2RangeFileFormat mFileFormat;
+
+ private final int mSuffixSearchValue;
+
+ S2CellMatcher(SatS2RangeFileFormat fileFormat, int suffixSearchValue) {
+ mFileFormat = Objects.requireNonNull(fileFormat);
+ mSuffixSearchValue = suffixSearchValue;
+ }
+
+ @Override
+ public int compare(int key, int value) {
+ int rangeStartCellIdOffset = key;
+ if (mSuffixSearchValue < rangeStartCellIdOffset) {
+ return -1;
+ } else {
+ int rangeLength = mFileFormat.extractRangeLengthFromTableEntryValue(value);
+ int rangeEndCellIdOffset = rangeStartCellIdOffset + rangeLength;
+ if (mSuffixSearchValue >= rangeEndCellIdOffset) {
+ return 1;
+ } else {
+ return 0;
+ }
+ }
+ }
+ }
+
+ /**
+ * An entry from the {@link SuffixTableBlock}. Use {@link #getSuffixTableRange()} to get the
+ * full, interpreted entry data.
+ */
+ public final class Entry extends SuffixTableBlock.Entry {
+
+ private final IntValueTable.TableEntry mSuffixTableEntry;
+
+ private S2LevelRange mSuffixTableRange;
+
+ Entry(IntValueTable.TableEntry suffixTableEntry) {
+ mSuffixTableEntry = Objects.requireNonNull(suffixTableEntry);
+ }
+
+ @Override
+ public int getIndex() {
+ return mSuffixTableEntry.getIndex();
+ }
+
+ /** Returns the data for this entry. */
+ @Override
+ public S2LevelRange getSuffixTableRange() {
+ // Creating SuffixTableRange is relatively expensive so it is created lazily and
+ // memoized.
+ if (mSuffixTableRange == null) {
+ // Create the range to return.
+ int startCellIdSuffix = mSuffixTableEntry.getKey();
+ checkStateInRange("startCellIdSuffixBits", startCellIdSuffix,
+ "minSuffixValue", 0, "maxSuffixValue", mFileFormat.getMaxSuffixValue());
+ long startCellId = mFileFormat.createCellId(mPrefix, startCellIdSuffix);
+
+ int tableEntryValue = mSuffixTableEntry.getValue();
+ int rangeLength =
+ mFileFormat.extractRangeLengthFromTableEntryValue(tableEntryValue);
+ checkStateInRange("rangeLength", rangeLength, "minRangeLength", 0, "maxRangeLength",
+ mFileFormat.getTableEntryMaxRangeLengthValue());
+ int endCellIdSuffix = startCellIdSuffix + rangeLength;
+
+ int endCellPrefixValue = mPrefix;
+ if (endCellIdSuffix > mFileFormat.getMaxSuffixValue()) {
+ // Handle the special case where the range ends in the next prefix. This is
+ // because the range end is exclusive, so the end value is allowed to be first
+ // cell ID from the next prefix.
+ if (endCellIdSuffix != mFileFormat.getMaxSuffixValue() + 1) {
+ throw new IllegalStateException("Range exceeds allowable cell IDs:"
+ + " startCellId=" + cellIdToString(startCellId)
+ + ", rangeLength=" + rangeLength);
+ }
+ endCellPrefixValue += 1;
+
+ // Check to see if the face ID has overflowed, and wrap to face zero if it has.
+ if (mFileFormat.extractFaceIdFromPrefix(endCellPrefixValue) > MAX_FACE_ID) {
+ endCellPrefixValue = 0;
+ }
+ endCellIdSuffix = 0;
+ }
+ long endCellId = mFileFormat.createCellId(endCellPrefixValue, endCellIdSuffix);
+ mSuffixTableRange = new S2LevelRange(startCellId, endCellId);
+ }
+ return mSuffixTableRange;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (o == null || getClass() != o.getClass()) {
+ return false;
+ }
+ Entry entry = (Entry) o;
+ return mSuffixTableEntry.equals(entry.mSuffixTableEntry);
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(mSuffixTableEntry);
+ }
+
+ @Override
+ public String toString() {
+ return "Entry{"
+ + "mSuffixTableEntry=" + mSuffixTableEntry
+ + '}';
+ }
+ }
+}
diff --git a/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SatS2RangeFileFormat.java b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SatS2RangeFileFormat.java
new file mode 100644
index 0000000..39507aa
--- /dev/null
+++ b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SatS2RangeFileFormat.java
@@ -0,0 +1,401 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range.read;
+
+import static com.android.storage.s2.S2Support.FACE_BIT_COUNT;
+import static com.android.storage.s2.S2Support.MAX_FACE_ID;
+import static com.android.storage.s2.S2Support.MAX_S2_LEVEL;
+
+import com.android.storage.s2.S2Support;
+import com.android.storage.util.BitwiseUtils;
+import com.android.storage.util.Conditions;
+
+import java.util.Objects;
+
+/**
+ * Holds information about the format of a satellite S2 data file, which is a type of block file
+ * (see {@link com.android.storage.block.read.BlockFileReader}).
+ * Some information is hardcoded and some is parameterized using information read from the file's
+ * header block. This class contains useful methods for validation, interpretation and storage of
+ * data in a file with the specified format.
+ */
+public final class SatS2RangeFileFormat {
+
+ /** The block type of the satellite S2 data file header (held in block 0). */
+ public static final int BLOCK_TYPE_HEADER = 1;
+
+ /**
+ * The block type used for padding between the header and suffix tables that allows for future
+ * expansion. See {@link #getSuffixTableBlockIdOffset()}.
+ */
+ public static final int BLOCK_TYPE_PADDING = 20;
+
+ /** The block type of a populated suffix table. */
+ public static final int BLOCK_TYPE_SUFFIX_TABLE = 10;
+
+ /** The expected magic value of a satellite S2 data file. */
+ public static final char MAGIC = 0xCFAF;
+
+ /** The format version of the satellite S2 data file, read and written. */
+ public static final int VERSION = 1;
+
+ private final int mDataS2Level;
+
+ private final int mPrefixBitCount;
+
+ private final int mMaxPrefixValue;
+
+ private final int mSuffixTableBlockIdOffset;
+
+ private final int mSuffixBitCount;
+
+ private final int mMaxSuffixValue;
+
+ private final int mTableEntryByteCount;
+
+ private final int mTableEntryBitCount;
+
+ private final int mTableEntryRangeLengthBitCount;
+
+ private final int mTableEntryMaxRangeLengthValue;
+
+ /**
+ * The number of bits in a cell ID of the data storage level that have fixed values, i.e. the
+ * final "1" followed by all zeros.
+ */
+ private final int mUnusedCellIdBitCount;
+
+ /**
+ * Whether the satellite S2 file contains an allowed list of S2 cells.
+ * {@code true} means allowed list.
+ * {@code false} means disallowed list.
+ */
+ private final boolean mIsAllowedList;
+
+ /**
+ * Creates a new file format. This constructor validates the values against various hard-coded
+ * constraints and will throw an {@link IllegalArgumentException} if they are not satisfied.
+ */
+ public SatS2RangeFileFormat(int s2Level, int prefixBitCount, int suffixBitCount,
+ int suffixTableBlockIdOffset, int tableEntryBitCount, boolean isAllowedList) {
+
+ Conditions.checkArgInRange("s2Level", s2Level, 0, MAX_S2_LEVEL);
+
+ // prefixBitCount must include at least the face bits and one more, it makes the logic
+ // for mMaxPrefixValue easier below. We also assume that prefix and suffix will be 31-bits
+ // as that makes sure they can be represented, unsigned in a Java int. A prefix / suffix
+ // of 31-bits (each) should be enough for anyone(TM). 31-bits = ~15 S2 levels.
+ // Anything more than level 18 for geo data (i.e. prefix PLUS suffix) will be very
+ // detailed, so it's unlikely this constraint will be a problem.
+ Conditions.checkArgInRange("prefixBitCount", prefixBitCount, 4, Integer.SIZE - 1);
+
+ // The suffix table uses fixed length records that are broken into a key and a value. The
+ // implementation requires the key is an unsigned int value, i.e. 31-bits, and the value can
+ // be held in an int value.
+
+ // The key of a suffix table entry is used to store the suffix for the cell ID at the start
+ // of a range of S2 cells (the prefix for that cell ID is implicit and the same for every
+ // entry in the table, see prefixBitCount).
+ int tableEntryKeyBitCount = suffixBitCount;
+ Conditions.checkArgInRange(
+ "tableEntryKeyBitCount", tableEntryKeyBitCount, 1, Integer.SIZE - 1);
+
+ // The value of a suffix table entry is used to hold both the range length and the entry
+ // value. See methods below that extract these components from an int. Hence, we check they
+ // will fit.
+ int tableEntryValueBitCount = tableEntryBitCount - tableEntryKeyBitCount;
+ Conditions.checkArgInRange(
+ "tableEntryValueBitCount", tableEntryValueBitCount, 1, Integer.SIZE);
+
+ if (S2Support.storageBitCountForLevel(s2Level) != prefixBitCount + suffixBitCount) {
+ // s2Level implies cellIds have a certain number of "storage bits", the prefix and
+ // suffix must consume all the bits.
+ throw new IllegalArgumentException("prefixBitCount=" + prefixBitCount
+ + " + suffixBitCount=" + suffixBitCount + " must be correct for the s2Level ("
+ + S2Support.storageBitCountForLevel(s2Level) + ")");
+ }
+ if (suffixTableBlockIdOffset < 1) {
+ // The format includes a header block, so there will always be an adjustment for at
+ // least that one block.
+ throw new IllegalArgumentException(
+ "suffixTableBlockIdOffset=" + suffixTableBlockIdOffset + " must be >= 1");
+ }
+ if (tableEntryBitCount < 0 || tableEntryBitCount % Byte.SIZE != 0
+ || tableEntryBitCount > Long.SIZE) {
+ // The classes used to read suffix tables only support entries that are a multiples of
+ // a byte. They also restrict to up a maximum of 8-bytes per table entry.
+ throw new IllegalArgumentException(
+ "suffixTableEntryBitCount=" + tableEntryBitCount
+ + " must be >= 0, be divisible by 8, and be no more than 64 bits");
+ }
+
+ // Everything in a suffix table entry that isn't the suffix is the range length, so we can
+ // calculate it from the information given.
+ int entryRangeLengthBitCount = tableEntryBitCount - suffixBitCount;
+ // For simplicity below we ensure we can hold the maximum range length value in an unsigned
+ // Java int, so up to 31-bits.
+ Conditions.checkArgInRange(
+ "entryRangeLengthBitCount", entryRangeLengthBitCount, 2, Integer.SIZE - 1);
+
+ // Set all the fields. The fields are either set directly from parameters or derived from
+ // the values given.
+
+ mDataS2Level = s2Level;
+ mPrefixBitCount = prefixBitCount;
+
+ // Prefix value: contains the face ID plus one or more bits for the index.
+ int cellIdIndexBitCount = prefixBitCount - FACE_BIT_COUNT;
+ mMaxPrefixValue = (int)
+ ((((long) MAX_FACE_ID) << cellIdIndexBitCount)
+ | BitwiseUtils.maxUnsignedValue(cellIdIndexBitCount));
+
+ mSuffixBitCount = suffixBitCount;
+ mMaxSuffixValue = (int) BitwiseUtils.maxUnsignedValue(suffixBitCount);
+
+ // prefixBitCount + suffixBitCount are all the "useful" bits. The remaining bits in a 64-bit
+ // cell ID are the trailing "1" (which we don't need to store) and the rest are zeros.
+ mUnusedCellIdBitCount = Long.SIZE - (prefixBitCount + suffixBitCount);
+
+ mTableEntryBitCount = tableEntryBitCount;
+ mTableEntryByteCount = tableEntryBitCount / 8;
+
+ mTableEntryRangeLengthBitCount = entryRangeLengthBitCount;
+ mTableEntryMaxRangeLengthValue =
+ (int) BitwiseUtils.maxUnsignedValue(entryRangeLengthBitCount);
+
+ mSuffixTableBlockIdOffset = suffixTableBlockIdOffset;
+
+ mIsAllowedList = isAllowedList;
+ }
+
+ /** Returns the S2 level of all geo data stored in the file. */
+ public int getS2Level() {
+ return mDataS2Level;
+ }
+
+ /**
+ * Returns the number of prefix bits from an S2 cell ID used to identify the block containing
+ * ranges.
+ */
+ public int getPrefixBitCount() {
+ return mPrefixBitCount;
+ }
+
+ /**
+ * Returns the maximum valid value that {@link #getPrefixBitCount()} can represent. Note: This
+ * is not just the number of bits: the prefix contains the face ID which can only be 0 - 5
+ * (inclusive).
+ */
+ public int getMaxPrefixValue() {
+ return mMaxPrefixValue;
+ }
+
+ /**
+ * Returns the number of "useful" bits of an S2 cell ID in the data after
+ * {@link #getPrefixBitCount()}, i.e. not including the trailing "1".
+ * Dependent on the {@link #getS2Level()}, which dictates the number of storage bits in every
+ * cell ID in a file, and {@link #getPrefixBitCount()}.
+ */
+ public int getSuffixBitCount() {
+ return mSuffixBitCount;
+ }
+
+ /**
+ * Returns the maximum value that {@link #getSuffixBitCount()} can represent.
+ */
+ public int getMaxSuffixValue() {
+ return mMaxSuffixValue;
+ }
+
+ /**
+ * Returns the number of bits in each suffix table entry. i.e.
+ * {@link #getTableEntryByteCount()} * 8
+ */
+ public int getTableEntryBitCount() {
+ return mTableEntryBitCount;
+ }
+
+ /** Returns the number of bytes in each suffix table entry. */
+ public int getTableEntryByteCount() {
+ return mTableEntryByteCount;
+ }
+
+ /** Return the number of bits in each suffix table entry used to store the length of a range. */
+ public int getTableEntryRangeLengthBitCount() {
+ return mTableEntryRangeLengthBitCount;
+ }
+
+ /** Returns the maximum value that {@link #getTableEntryRangeLengthBitCount()} can represent. */
+ public int getTableEntryMaxRangeLengthValue() {
+ return mTableEntryMaxRangeLengthValue;
+ }
+
+ /**
+ * Returns the offset to apply to the prefix value to compute the block ID holding the data for
+ * that prefix. Always >= 1 to account for the header block.
+ */
+ public int getSuffixTableBlockIdOffset() {
+ return mSuffixTableBlockIdOffset;
+ }
+
+ /**
+ * @return {@code true} if the satellite S2 file contains an allowed list of S2 cells.
+ * {@code false} if the satellite S2 file contains a disallowed list of S2 cells.
+ */
+ public boolean isAllowedList() {
+ return mIsAllowedList;
+ }
+
+ /** Extracts the prefix bits from a cell ID and returns them as an unsigned int. */
+ public int extractPrefixValueFromCellId(long cellId) {
+ checkS2Level("cellId", cellId);
+ return (int) (cellId >>> (mSuffixBitCount + mUnusedCellIdBitCount));
+ }
+
+ /** Extracts the suffix bits from a cell ID and returns them as an unsigned int. */
+ public int extractSuffixValueFromCellId(long cellId) {
+ checkS2Level("cellId", cellId);
+ return (int) (cellId >>> (mUnusedCellIdBitCount)) & mMaxSuffixValue;
+ }
+
+ /** Extracts the range length from a table entry value. */
+ public int extractRangeLengthFromTableEntryValue(int value) {
+ long mask = BitwiseUtils.getLowBitsMask(mTableEntryRangeLengthBitCount);
+ return (int) (value & mask);
+ }
+
+ /** Creates a table entry value from a range length. */
+ public long createSuffixTableValue(int rangeLength) {
+ Conditions.checkArgInRange(
+ "rangeLength", rangeLength, 0, getTableEntryMaxRangeLengthValue());
+ return rangeLength;
+ }
+
+ /** Creates a cell ID from a prefix and a suffix component. */
+ public long createCellId(int prefixValue, int suffixValue) {
+ Conditions.checkArgInRange("prefixValue", prefixValue, 0, mMaxPrefixValue);
+ Conditions.checkArgInRange("suffixValue", suffixValue, 0, mMaxSuffixValue);
+ long cellId = prefixValue;
+ cellId <<= mSuffixBitCount;
+ cellId |= suffixValue;
+ cellId <<= 1;
+ cellId |= 1;
+ cellId <<= mUnusedCellIdBitCount - 1;
+
+ checkS2Level("cellId", cellId);
+ return cellId;
+ }
+
+ /** Extracts the face ID bits from a prefix value. */
+ public int extractFaceIdFromPrefix(int prefixValue) {
+ return prefixValue >>> (mPrefixBitCount - FACE_BIT_COUNT);
+ }
+
+ /**
+ * Calculates the number of cell IDs in the given range. Throws {@link IllegalArgumentException}
+ * if {@code rangeStartCellId} is "higher" than {@code rangeEndCellId} or the range length would
+ * be outside of the int range.
+ *
+ * @param rangeStartCellId the start of the range (inclusive)
+ * @param rangeEndCellId the end of the range (exclusive)
+ */
+ public int calculateRangeLength(long rangeStartCellId, long rangeEndCellId) {
+ checkS2Level("rangeStartCellId", rangeStartCellId);
+ checkS2Level("rangeEndCellId", rangeEndCellId);
+
+ // Convert to numeric values that can just be subtracted without worrying about sign
+ // issues.
+ long rangeEndCellIdNumeric = rangeEndCellId >>> mUnusedCellIdBitCount;
+ long rangeStartCellIdNumeric = rangeStartCellId >>> mUnusedCellIdBitCount;
+ if (rangeStartCellIdNumeric >= rangeEndCellIdNumeric) {
+ throw new IllegalArgumentException(
+ "rangeStartCellId=" + cellIdToString(rangeStartCellId)
+ + " is >= rangeEndCellId=" + cellIdToString(rangeEndCellId));
+ }
+ long differenceNumeric = rangeEndCellIdNumeric - rangeStartCellIdNumeric;
+ if (differenceNumeric < 0 || differenceNumeric > Integer.MAX_VALUE) {
+ throw new IllegalArgumentException("rangeLength=" + differenceNumeric
+ + " is outside of expected range");
+ }
+ return (int) differenceNumeric;
+ }
+
+ /** Formats a cellId in terms of prefix and suffix values. */
+ public String cellIdToString(long cellId) {
+ int prefix = extractPrefixValueFromCellId(cellId);
+ int suffix = extractSuffixValueFromCellId(cellId);
+ String prefixBitsString = BitwiseUtils.toUnsignedString(mPrefixBitCount, prefix);
+ String suffixBitsString = BitwiseUtils.toUnsignedString(mSuffixBitCount, suffix);
+ return "cellId{prefix=" + prefix + " (" + prefixBitsString + ")"
+ + ", suffix=" + suffix + " (" + suffixBitsString + ")"
+ + "}";
+ }
+
+ @Override
+ public String toString() {
+ return "SatS2RangeFileFormat{"
+ + "mDataS2Level=" + mDataS2Level
+ + ", mPrefixBitCount=" + mPrefixBitCount
+ + ", mMaxPrefixValue=" + mMaxPrefixValue
+ + ", mSuffixBitCount=" + mSuffixBitCount
+ + ", mMaxSuffixValue=" + mMaxSuffixValue
+ + ", mTableEntryBitCount=" + mTableEntryBitCount
+ + ", mTableEntryRangeLengthBitCount=" + mTableEntryRangeLengthBitCount
+ + ", mTableEntryMaxRangeLengthValue=" + mTableEntryMaxRangeLengthValue
+ + ", mSuffixTableBlockIdOffset=" + mSuffixTableBlockIdOffset
+ + ", mUnusedCellIdBitCount=" + mUnusedCellIdBitCount
+ + ", mIsAllowedList=" + mIsAllowedList
+ + '}';
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (o == null || getClass() != o.getClass()) {
+ return false;
+ }
+ SatS2RangeFileFormat that = (SatS2RangeFileFormat) o;
+ return mDataS2Level == that.mDataS2Level
+ && mPrefixBitCount == that.mPrefixBitCount
+ && mMaxPrefixValue == that.mMaxPrefixValue
+ && mSuffixBitCount == that.mSuffixBitCount
+ && mMaxSuffixValue == that.mMaxSuffixValue
+ && mTableEntryBitCount == that.mTableEntryBitCount
+ && mTableEntryRangeLengthBitCount == that.mTableEntryRangeLengthBitCount
+ && mTableEntryMaxRangeLengthValue == that.mTableEntryMaxRangeLengthValue
+ && mSuffixTableBlockIdOffset == that.mSuffixTableBlockIdOffset
+ && mIsAllowedList == that.mIsAllowedList
+ && mUnusedCellIdBitCount == that.mUnusedCellIdBitCount;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(mDataS2Level, mPrefixBitCount, mMaxPrefixValue, mSuffixBitCount,
+ mMaxSuffixValue, mTableEntryBitCount, mTableEntryRangeLengthBitCount,
+ mTableEntryMaxRangeLengthValue, mSuffixTableBlockIdOffset, mIsAllowedList,
+ mUnusedCellIdBitCount);
+ }
+
+ private void checkS2Level(String name, long cellId) {
+ if (S2Support.getS2Level(cellId) != mDataS2Level) {
+ throw new IllegalArgumentException(
+ name + "=" + S2Support.cellIdToString(cellId) + " is at the wrong level");
+ }
+ }
+}
diff --git a/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SatS2RangeFileReader.java b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SatS2RangeFileReader.java
new file mode 100644
index 0000000..ecfa0a9
--- /dev/null
+++ b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SatS2RangeFileReader.java
@@ -0,0 +1,218 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range.read;
+
+import com.android.storage.block.read.Block;
+import com.android.storage.block.read.BlockFileReader;
+import com.android.storage.block.read.BlockInfo;
+import com.android.storage.s2.S2LevelRange;
+import com.android.storage.s2.S2Support;
+import com.android.storage.util.Conditions;
+import com.android.storage.util.Visitor;
+
+import java.io.File;
+import java.io.IOException;
+import java.util.Objects;
+
+/** Provides access to the content of a satellite S2 data file. */
+public final class SatS2RangeFileReader implements AutoCloseable {
+
+ private final BlockFileReader mBlockFileReader;
+
+ private HeaderBlock mHeaderBlock;
+
+ private SuffixTableExtraInfo[] mSuffixTableExtraInfos;
+
+ /** Convenience field to avoid calling {@link HeaderBlock#getFileFormat()} repeatedly. */
+ private SatS2RangeFileFormat mFileFormat;
+
+ private boolean mClosed;
+
+ private SatS2RangeFileReader(BlockFileReader blockFileReader) {
+ mBlockFileReader = Objects.requireNonNull(blockFileReader);
+ }
+
+ /**
+ * Opens the specified file. Throws {@link IOException} in the event of a access problem reading
+ * the file. Throws {@link IllegalArgumentException} if the file has a format / syntax problem.
+ *
+ * <p>After open, use methods like {@link #findEntryByCellId(long)} to access the data.
+ */
+ public static SatS2RangeFileReader open(File file) throws IOException {
+ boolean memoryMapBlocks = false;
+ BlockFileReader blockFileReader = BlockFileReader.open(
+ memoryMapBlocks, file, SatS2RangeFileFormat.MAGIC, SatS2RangeFileFormat.VERSION);
+ SatS2RangeFileReader satS2RangeFileReader = new SatS2RangeFileReader(blockFileReader);
+ satS2RangeFileReader.initialize();
+ return satS2RangeFileReader;
+ }
+
+ private void initialize() throws IOException {
+ // Check the BlockInfo for the header block is what we expect.
+ int headerBlockId = 0;
+ BlockInfo firstBlockInfo = mBlockFileReader.getBlockInfo(headerBlockId);
+ if (firstBlockInfo.getType() != SatS2RangeFileFormat.BLOCK_TYPE_HEADER) {
+ throw new IllegalArgumentException("headerBlockInfo.getType()="
+ + firstBlockInfo.getType() + " must be "
+ + SatS2RangeFileFormat.BLOCK_TYPE_HEADER);
+ }
+
+ // So far so good. Open the header block itself and extract the information held there.
+ Block firstBlock = mBlockFileReader.getBlock(headerBlockId);
+ if (firstBlock.getType() != SatS2RangeFileFormat.BLOCK_TYPE_HEADER) {
+ throw new IllegalArgumentException("firstBlock.getType()=" + firstBlock.getType()
+ + " must be " + SatS2RangeFileFormat.BLOCK_TYPE_HEADER);
+ }
+ mHeaderBlock = HeaderBlock.wrap(firstBlock.getData());
+
+ // Optimization: hold a direct reference to fileFormat since it is referenced often.
+ mFileFormat = mHeaderBlock.getFileFormat();
+
+ // Read all the BlockInfos for data blocks and precache the SuffixTableBlock.Info instances.
+ mSuffixTableExtraInfos = new SuffixTableExtraInfo[mFileFormat.getMaxPrefixValue() + 1];
+ for (int prefix = 0; prefix < mSuffixTableExtraInfos.length; prefix++) {
+ int blockId = prefix + mFileFormat.getSuffixTableBlockIdOffset();
+ BlockInfo blockInfo = mBlockFileReader.getBlockInfo(blockId);
+ int type = blockInfo.getType();
+ if (type == SatS2RangeFileFormat.BLOCK_TYPE_SUFFIX_TABLE) {
+ mSuffixTableExtraInfos[prefix] =
+ SuffixTableExtraInfo.create(mFileFormat, blockInfo);
+ } else {
+ throw new IllegalStateException("Unknown block type=" + type);
+ }
+ }
+ }
+
+ /** A {@link Visitor} for the {@link SatS2RangeFileReader}. See {@link #visit} */
+ public interface SatS2RangeFileVisitor extends Visitor {
+
+ /** Called after {@link #begin()}, once only. */
+ void visitHeaderBlock(HeaderBlock headerBlock) throws VisitException;
+
+ /**
+ * Called after {@link #visitHeaderBlock(HeaderBlock)}}, once for each suffix table in the
+ * file.
+ */
+ void visitSuffixTableExtraInfo(SuffixTableExtraInfo suffixTableExtraInfo)
+ throws VisitException;
+
+ /**
+ * Called after {@link #visitHeaderBlock(HeaderBlock)}, once per suffix table in the file.
+ */
+ void visitSuffixTableBlock(SuffixTableBlock suffixTableBlock) throws VisitException;
+ }
+
+ /**
+ * Issues callbacks to the supplied {@link SatS2RangeFileVisitor} containing information from
+ * the satellite S2 data file.
+ */
+ public void visit(SatS2RangeFileVisitor visitor) throws Visitor.VisitException {
+ try {
+ visitor.begin();
+
+ visitor.visitHeaderBlock(mHeaderBlock);
+
+ for (int i = 0; i < mSuffixTableExtraInfos.length; i++) {
+ visitor.visitSuffixTableExtraInfo(mSuffixTableExtraInfos[i]);
+ }
+
+ try {
+ for (int i = 0; i < mSuffixTableExtraInfos.length; i++) {
+ SuffixTableBlock suffixTableBlock = getSuffixTableBlockForPrefix(i);
+ visitor.visitSuffixTableBlock(suffixTableBlock);
+ }
+ } catch (IOException e) {
+ throw new Visitor.VisitException(e);
+ }
+ } finally {
+ visitor.end();
+ }
+ }
+
+ /**
+ * Finds an {@link S2LevelRange} associated with a range covering {@code cellId}.
+ * Returns {@code null} if no range exists. Throws {@link IllegalArgumentException} if
+ * {@code cellId} is not the correct S2 level for the file. See {@link #getS2Level()}.
+ */
+ public S2LevelRange findEntryByCellId(long cellId) throws IOException {
+ checkNotClosed();
+ int dataS2Level = mFileFormat.getS2Level();
+ int searchS2Level = S2Support.getS2Level(cellId);
+ if (dataS2Level != searchS2Level) {
+ throw new IllegalArgumentException(
+ "data S2 level=" + dataS2Level + ", search S2 level=" + searchS2Level);
+ }
+
+ int prefix = mFileFormat.extractPrefixValueFromCellId(cellId);
+ SuffixTableBlock suffixTableBlock = getSuffixTableBlockForPrefix(prefix);
+ SuffixTableBlock.Entry suffixTableEntry = suffixTableBlock.findEntryByCellId(cellId);
+ if (suffixTableEntry == null) {
+ return null;
+ }
+ return suffixTableEntry.getSuffixTableRange();
+ }
+
+ private SuffixTableExtraInfo getSuffixTableExtraInfoForPrefix(int prefixValue) {
+ Conditions.checkArgInRange(
+ "prefixValue", prefixValue, "minPrefixValue", 0, "maxPrefixValue",
+ mFileFormat.getMaxPrefixValue());
+
+ return mSuffixTableExtraInfos[prefixValue];
+ }
+
+ private SuffixTableBlock getSuffixTableBlockForPrefix(int prefix) throws IOException {
+ SuffixTableExtraInfo suffixTableExtraInfo = getSuffixTableExtraInfoForPrefix(prefix);
+ if (suffixTableExtraInfo.isEmpty()) {
+ return SuffixTableBlock.createEmpty(mFileFormat, prefix);
+ }
+ Block block = mBlockFileReader.getBlock(prefix + mFileFormat.getSuffixTableBlockIdOffset());
+ SuffixTableBlock suffixTableBlock =
+ SuffixTableBlock.createPopulated(mFileFormat, block.getData());
+ if (prefix != suffixTableBlock.getPrefix()) {
+ throw new IllegalArgumentException("prefixValue=" + prefix
+ + " != suffixTableBlock.getPrefix()=" + suffixTableBlock.getPrefix());
+ }
+ return suffixTableBlock;
+ }
+
+ @Override
+ public void close() throws IOException {
+ mClosed = true;
+ mHeaderBlock = null;
+ mBlockFileReader.close();
+ }
+
+ private void checkNotClosed() throws IOException {
+ if (mClosed) {
+ throw new IOException("Closed");
+ }
+ }
+
+ /** Returns the S2 level for the file. See also {@link #findEntryByCellId(long)}. */
+ public int getS2Level() throws IOException {
+ checkNotClosed();
+ return mHeaderBlock.getFileFormat().getS2Level();
+ }
+
+ /**
+ * @return {@code true} if the satellite S2 file contains an allowed list of S2 cells.
+ * {@code false} if the satellite S2 file contains a disallowed list of S2 cells.
+ */
+ public boolean isAllowedList() {
+ return mFileFormat.isAllowedList();
+ }
+}
diff --git a/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SuffixTableBlock.java b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SuffixTableBlock.java
new file mode 100644
index 0000000..1a6fad7
--- /dev/null
+++ b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SuffixTableBlock.java
@@ -0,0 +1,185 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range.read;
+
+import static com.android.storage.s2.S2Support.cellIdToString;
+import static com.android.storage.s2.S2Support.getS2Level;
+
+import com.android.storage.block.read.BlockData;
+import com.android.storage.s2.S2LevelRange;
+import com.android.storage.table.packed.read.IntValueTypedPackedTable;
+import com.android.storage.util.BitwiseUtils;
+import com.android.storage.util.Visitor;
+
+import java.util.Objects;
+
+/**
+ * The main type of block for a satellite S2 data file.
+ *
+ * <p>Logically, each suffix table block holds zero or more entries for S2 ranges, e.g.:
+ * <pre>
+ * startCellId=X, endCellId=Y
+ * </pre>
+ *
+ * <p>Tables are generated so that all entries in the table have the same S2 level and "prefix
+ * bits" for the S2 cell IDs they describe, i.e. if the table's assigned prefix is "1011000", then
+ * every cell ID included in every range entry (i.e. from X to Y) must start with "1011000". The
+ * entries in the table are ordered by startCellId and ranges cannot overlap. There is only one
+ * block / suffix table for each possible prefix.
+ *
+ * <p>Note that because the endCellId is <em>exclusive</em>, the last entry's endCellId <em>can</em>
+ * refer the first S2 cell ID from the next prefix, or wrap around to face 0 for the last entry
+ * for face ID 5.
+ *
+ * <p>Any S2 cell id with a prefix that is not covered by a range entry in the associated table can
+ * be inferred to have a value of zero.
+ *
+ * <p>Entries can be obtained by called methods such as {@link #getEntryByIndex(int)},
+ * {@link #findEntryByCellId(long)}.
+ */
+public final class SuffixTableBlock {
+
+ private final SatS2RangeFileFormat mFileFormat;
+
+ private final SuffixTableBlockDelegate mDelegate;
+
+ private final int mPrefix;
+
+ /**
+ * The implementation of the suffix table block. Suffix table blocks have two main
+ * implementations: zero-length blocks used to represent empty tables, and blocks containing
+ * {@link IntValueTypedPackedTable} data. Since they are so different they are implemented
+ * independently.
+ */
+ interface SuffixTableBlockDelegate {
+
+ /** Returns the prefix for cell IDs in this table. */
+ int getPrefix();
+
+ /**
+ * Returns the entry containing the specified cell ID, or {@code null} if there isn't one.
+ */
+ Entry findEntryByCellId(long cellId);
+
+ /**
+ * Returns the entry with the specified index. Throws {@link IndexOutOfBoundsException} if
+ * the index is invalid.
+ */
+ Entry findEntryByIndex(int i);
+
+ /** Returns the number of entries in the table. */
+ int getEntryCount();
+ }
+
+ private SuffixTableBlock(SatS2RangeFileFormat fileFormat, SuffixTableBlockDelegate delegate) {
+ mFileFormat = Objects.requireNonNull(fileFormat);
+ mDelegate = Objects.requireNonNull(delegate);
+ mPrefix = delegate.getPrefix();
+ }
+
+ /**
+ * Creates a populated {@link SuffixTableBlock} by interpreting {@link BlockData} and using
+ * the supplied format information.
+ */
+ public static SuffixTableBlock createPopulated(
+ SatS2RangeFileFormat fileFormat, BlockData blockData) {
+ if (blockData.getSize() == 0) {
+ throw new IllegalArgumentException("blockData=" + blockData + ", is zero length");
+ }
+ IntValueTypedPackedTable packedTable = new IntValueTypedPackedTable(blockData);
+ PopulatedSuffixTableBlock delegate = new PopulatedSuffixTableBlock(fileFormat, packedTable);
+ return new SuffixTableBlock(fileFormat, delegate);
+ }
+
+ /**
+ * Creates an unpopulated {@link SuffixTableBlock} for the supplied prefix and using
+ * the supplied format information.
+ */
+ public static SuffixTableBlock createEmpty(SatS2RangeFileFormat fileFormat, int prefix) {
+ return new SuffixTableBlock(fileFormat, new UnpopulatedSuffixTableBlock(prefix));
+ }
+
+ /** Returns the prefix for this table. */
+ public int getPrefix() {
+ return mDelegate.getPrefix();
+ }
+
+ /**
+ * Returns the entry for a given cell ID or {@code null} if there isn't one. The
+ * {@code cellId} must be the same level as the table and have the same prefix otherwise an
+ * {@link IllegalArgumentException} is thrown.
+ */
+ public Entry findEntryByCellId(long cellId) {
+ if (getS2Level(cellId) != mFileFormat.getS2Level()) {
+ throw new IllegalArgumentException(
+ cellIdToString(cellId) + " s2 level is not "
+ + mFileFormat.getS2Level());
+ }
+ if (mFileFormat.extractPrefixValueFromCellId(cellId) != mPrefix) {
+ String prefixBitString =
+ BitwiseUtils.toUnsignedString(mFileFormat.getPrefixBitCount(), mPrefix);
+ throw new IllegalArgumentException(
+ cellId + "(" + mFileFormat.cellIdToString(cellId)
+ + ") does not have prefix bits " + mPrefix
+ + " (" + prefixBitString + ")");
+ }
+
+ return mDelegate.findEntryByCellId(cellId);
+ }
+
+ /** Returns the entry at the specified index. */
+ public Entry getEntryByIndex(int i) {
+ return mDelegate.findEntryByIndex(i);
+ }
+
+ /** Returns the number of entries in the table. */
+ public int getEntryCount() {
+ return mDelegate.getEntryCount();
+ }
+
+ /** A {@link Visitor} for the {@link SuffixTableBlock}. See {@link #visit} */
+ public interface SuffixTableBlockVisitor extends Visitor {
+
+ /** Called after {@link #begin()}, once. */
+ void visit(SuffixTableBlock suffixTableBlock) throws VisitException;
+ }
+
+ /**
+ * Issues callbacks to the supplied {@link SuffixTableBlockVisitor}.
+ */
+ public void visit(SuffixTableBlockVisitor visitor) throws Visitor.VisitException {
+ try {
+ visitor.begin();
+ visitor.visit(this);
+ } finally {
+ visitor.end();
+ }
+ }
+
+ /**
+ * An entry from the {@link SuffixTableBlock}. Use {@link #getSuffixTableRange()} to get the
+ * full, interpreted entry data.
+ */
+ public abstract static class Entry {
+
+ /** Returns the position of this entry in the table. */
+ public abstract int getIndex();
+
+ /** Returns the data for this entry. */
+ public abstract S2LevelRange getSuffixTableRange();
+ }
+}
diff --git a/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SuffixTableExtraInfo.java b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SuffixTableExtraInfo.java
new file mode 100644
index 0000000..2b179fe
--- /dev/null
+++ b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SuffixTableExtraInfo.java
@@ -0,0 +1,103 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range.read;
+
+import com.android.storage.block.read.BlockInfo;
+import com.android.storage.io.read.TypedInputStream;
+import com.android.storage.util.Conditions;
+
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+
+/**
+ * Information about a suffix table block held in the header of a satellite S2 data file. It can be
+ * used to work out whether to read the associated block data.
+ */
+public final class SuffixTableExtraInfo {
+
+ /**
+ * The suffix table's S2 cell ID prefix. This information is not stored in the block info
+ * directly; during file read it is calculated from the block ID, i.e. {block id} - {suffix
+ * table block id offset}.
+ */
+ private final int mPrefix;
+
+ private final int mEntryCount;
+
+ /** Creates metadata about a suffix table. */
+ public SuffixTableExtraInfo(int prefix, int entryCount) {
+ if (prefix < 0) {
+ throw new IllegalArgumentException("prefix=" + prefix + " must be >= 0");
+ }
+ mPrefix = prefix;
+
+ if (entryCount < 0) {
+ throw new IllegalArgumentException("entryCount=" + entryCount + " must be >= 0");
+ }
+ mEntryCount = entryCount;
+ }
+
+ /**
+ * Creates a {@link SuffixTableExtraInfo} from a {@link BlockInfo}. Throws an
+ * {@link IllegalArgumentException} if the block info is the wrong type or malformed.
+ */
+ public static SuffixTableExtraInfo create(
+ SatS2RangeFileFormat fileFormat, BlockInfo blockInfo) {
+ if (blockInfo.getType() != SatS2RangeFileFormat.BLOCK_TYPE_SUFFIX_TABLE) {
+ throw new IllegalArgumentException("blockType=" + blockInfo.getType()
+ + " is not of expected type=" + SatS2RangeFileFormat.BLOCK_TYPE_SUFFIX_TABLE);
+ }
+ int prefix = blockInfo.getId() - fileFormat.getSuffixTableBlockIdOffset();
+ if (blockInfo.getBlockSizeBytes() == 0) {
+ // Empty blocks have no data and no extra bytes but we know they have zero elements.
+ return new SuffixTableExtraInfo(prefix, 0 /* entryCount */);
+ }
+
+ byte[] extraBytes = blockInfo.getExtraBytes();
+ if (extraBytes == null || extraBytes.length == 0) {
+ throw new IllegalArgumentException(
+ "Extra bytes null or empty in blockInfo=" + blockInfo);
+ }
+
+ try (TypedInputStream typedInputStream = new TypedInputStream(
+ new ByteArrayInputStream(extraBytes))) {
+ int entryCount = typedInputStream.readInt();
+ Conditions.checkStateInRange(
+ "entryCount", entryCount, "minSuffixValue", 0, "maxSuffixValue",
+ fileFormat.getMaxSuffixValue());
+ return new SuffixTableExtraInfo(prefix, entryCount);
+ } catch (IOException e) {
+ // This shouldn't happen with a byte[]
+ throw new IllegalStateException("Unexpected exception while reading a byte[]", e);
+ }
+ }
+
+ /** Returns the prefix of the associated suffix table. */
+ public int getPrefix() {
+ return mPrefix;
+ }
+
+ /** Returns the number of entries in the associated suffix table. */
+ public int getEntryCount() {
+ return mEntryCount;
+ }
+
+ /** Returns true if the number of entries in the associated suffix table is zero. */
+ public boolean isEmpty() {
+ return mEntryCount == 0;
+ }
+}
diff --git a/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SuffixTableSharedData.java b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SuffixTableSharedData.java
new file mode 100644
index 0000000..2221b2c
--- /dev/null
+++ b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/SuffixTableSharedData.java
@@ -0,0 +1,85 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range.read;
+
+import com.android.storage.io.read.TypedInputStream;
+import com.android.storage.table.reader.Table;
+
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+import java.util.Objects;
+
+/**
+ * Shared data for a suffix table held in a suffix table block: the information applies to all
+ * entries in the table and is required when interpreting the table's block data.
+ */
+public final class SuffixTableSharedData {
+
+ private final int mTablePrefix;
+
+ /**
+ * Creates a {@link SuffixTableSharedData}. See also {@link #fromBytes(byte[])}.
+ */
+ public SuffixTableSharedData(int tablePrefix) {
+ mTablePrefix = tablePrefix;
+ }
+
+ /**
+ * Returns the S2 cell ID prefix associated with the table. i.e. all S2 ranges in the table will
+ * have this prefix.
+ */
+ public int getTablePrefix() {
+ return mTablePrefix;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (o == null || getClass() != o.getClass()) {
+ return false;
+ }
+ SuffixTableSharedData that = (SuffixTableSharedData) o;
+ return mTablePrefix == that.mTablePrefix;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(mTablePrefix);
+ }
+
+ @Override
+ public String toString() {
+ return "SuffixTableSharedData{"
+ + "mTablePrefix=" + mTablePrefix
+ + '}';
+ }
+
+ /**
+ * Creates a {@link SuffixTableSharedData} using shared data from a {@link Table}.
+ */
+ public static SuffixTableSharedData fromBytes(byte[] bytes) {
+ try (ByteArrayInputStream bis = new ByteArrayInputStream(bytes);
+ TypedInputStream tis = new TypedInputStream(bis)) {
+ int tablePrefixValue = tis.readInt();
+ return new SuffixTableSharedData(tablePrefixValue);
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ }
+}
diff --git a/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/UnpopulatedSuffixTableBlock.java b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/UnpopulatedSuffixTableBlock.java
new file mode 100644
index 0000000..56730c2
--- /dev/null
+++ b/utils/satellite/s2storage/src/readonly/java/com/android/telephony/sats2range/read/UnpopulatedSuffixTableBlock.java
@@ -0,0 +1,50 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range.read;
+
+/**
+ * An implementation of {@link SuffixTableBlock.SuffixTableBlockDelegate} for tables that are not
+ * backed by real block data, i.e. have zero entries.
+ */
+final class UnpopulatedSuffixTableBlock implements SuffixTableBlock.SuffixTableBlockDelegate {
+
+ private final int mPrefix;
+
+ UnpopulatedSuffixTableBlock(int prefix) {
+ mPrefix = prefix;
+ }
+
+ @Override
+ public int getPrefix() {
+ return mPrefix;
+ }
+
+ @Override
+ public SuffixTableBlock.Entry findEntryByCellId(long cellId) {
+ return null;
+ }
+
+ @Override
+ public SuffixTableBlock.Entry findEntryByIndex(int i) {
+ throw new IndexOutOfBoundsException("Unpopulated table");
+ }
+
+ @Override
+ public int getEntryCount() {
+ return 0;
+ }
+}
diff --git a/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/HeaderBlockTest.java b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/HeaderBlockTest.java
new file mode 100644
index 0000000..e7bad01
--- /dev/null
+++ b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/HeaderBlockTest.java
@@ -0,0 +1,72 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range;
+
+import static org.junit.Assert.assertArrayEquals;
+import static org.junit.Assert.assertEquals;
+
+import com.android.storage.block.write.BlockWriter;
+import com.android.telephony.sats2range.read.HeaderBlock;
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+import com.android.telephony.sats2range.utils.TestUtils;
+import com.android.telephony.sats2range.write.HeaderBlockWriter;
+
+import org.junit.Test;
+import org.mockito.InOrder;
+import org.mockito.Mockito;
+
+import java.io.IOException;
+
+/** Tests for {@link HeaderBlockWriter} and {@link HeaderBlock}. */
+public class HeaderBlockTest {
+ @Test
+ public void readWrite() throws IOException {
+ SatS2RangeFileFormat fileFormat = TestUtils.createS2RangeFileFormat(true);
+
+ // Create header data using HeaderBlockWriter.
+ HeaderBlockWriter headerBlockWriter = HeaderBlockWriter.create(fileFormat);
+ BlockWriter.ReadBack readBack = headerBlockWriter.close();
+ assertEquals(SatS2RangeFileFormat.BLOCK_TYPE_HEADER, readBack.getType());
+ assertArrayEquals(new byte[0], readBack.getExtraBytes());
+
+ // Read the data back and confirm it matches what we expected.
+ HeaderBlock headerBlock = HeaderBlock.wrap(readBack.getBlockData());
+ assertEquals(fileFormat, headerBlock.getFileFormat());
+ }
+
+ @Test
+ public void visit() throws Exception {
+ SatS2RangeFileFormat fileFormat = TestUtils.createS2RangeFileFormat(true);
+
+ // Create header data using HeaderBlockWriter.
+ HeaderBlockWriter headerBlockWriter = HeaderBlockWriter.create(fileFormat);
+ BlockWriter.ReadBack readBack = headerBlockWriter.close();
+
+ // Read the data back and confirm it matches what we expected.
+ HeaderBlock headerBlock = HeaderBlock.wrap(readBack.getBlockData());
+
+ HeaderBlock.HeaderBlockVisitor mockVisitor =
+ Mockito.mock(HeaderBlock.HeaderBlockVisitor.class);
+
+ headerBlock.visit(mockVisitor);
+
+ InOrder inOrder = Mockito.inOrder(mockVisitor);
+ inOrder.verify(mockVisitor).begin();
+ inOrder.verify(mockVisitor).visitFileFormat(fileFormat);
+ inOrder.verify(mockVisitor).end();
+ }
+}
diff --git a/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/PushBackIteratorTest.java b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/PushBackIteratorTest.java
new file mode 100644
index 0000000..84a960a
--- /dev/null
+++ b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/PushBackIteratorTest.java
@@ -0,0 +1,97 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertThrows;
+import static org.junit.Assert.assertTrue;
+
+import com.android.telephony.sats2range.write.PushBackIterator;
+
+import org.junit.Test;
+
+import java.util.Arrays;
+import java.util.List;
+import java.util.NoSuchElementException;
+
+/** Tests for {@link PushBackIterator}. */
+public class PushBackIteratorTest {
+
+ @Test
+ public void test() {
+ List<String> values = listOf("One", "Two", "Three", "Four");
+ PushBackIterator<String> iterator = new PushBackIterator<>(values.iterator());
+ assertTrue(iterator.hasNext());
+
+ // iterator = One, Two, Three, Four
+ iterator.pushBack("Zero");
+ assertTrue(iterator.hasNext());
+ assertEquals("Zero", iterator.next());
+
+ // iterator = One, Two, Three, Four
+ assertTrue(iterator.hasNext());
+ assertEquals("One", iterator.next());
+
+ // iterator = Two, Three, Four
+ iterator.pushBack("One");
+ iterator.pushBack("Zero");
+ assertTrue(iterator.hasNext());
+ assertEquals("Zero", iterator.next());
+ assertTrue(iterator.hasNext());
+ assertEquals("One", iterator.next());
+
+ // iterator = Two, Three, Four
+ assertTrue(iterator.hasNext());
+ assertEquals("Two", iterator.next());
+ assertTrue(iterator.hasNext());
+ assertEquals("Three", iterator.next());
+ assertTrue(iterator.hasNext());
+ assertEquals("Four", iterator.next());
+ assertFalse(iterator.hasNext());
+
+ assertThrows(NoSuchElementException.class, iterator::next);
+
+ // iterator = Empty
+ iterator.pushBack("Four");
+ assertTrue(iterator.hasNext());
+ assertEquals("Four", iterator.next());
+ }
+
+ @Test
+ public void removeNotSupported() {
+ List<String> values = listOf("One", "Two", "Three", "Four");
+ PushBackIterator<String> iterator = new PushBackIterator<>(values.iterator());
+ assertEquals("One", iterator.next());
+
+ assertThrows(UnsupportedOperationException.class, iterator::remove);
+
+ iterator.pushBack("One");
+ iterator.pushBack("Zero");
+
+ assertThrows(UnsupportedOperationException.class, iterator::remove);
+
+ assertEquals("Zero", iterator.next());
+ assertThrows(UnsupportedOperationException.class, iterator::remove);
+ }
+
+ /** Returns a list from a varargs param. */
+ @SafeVarargs
+ private static <E> List<E> listOf(E... values) {
+ return Arrays.asList(values);
+ }
+}
diff --git a/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SatS2RangeFileFormatTest.java b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SatS2RangeFileFormatTest.java
new file mode 100644
index 0000000..80ef467
--- /dev/null
+++ b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SatS2RangeFileFormatTest.java
@@ -0,0 +1,171 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range;
+
+import static com.android.storage.s2.S2Support.cellId;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertThrows;
+import static org.junit.Assert.assertTrue;
+
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+
+import org.junit.Test;
+
+/** Tests for {@link SatS2RangeFileFormat}. */
+public class SatS2RangeFileFormatTest {
+ @Test
+ public void accessors() {
+ int s2Level = 12;
+ int prefixBitCount = 11;
+ int suffixBitCount = 16;
+ int suffixTableBlockIdOffset = 5;
+ int tableEntryBitCount = 24;
+ int entryRangeLengthBitCount = 8;
+ boolean isAllowedList = true;
+ SatS2RangeFileFormat satS2RangeFileFormat = new SatS2RangeFileFormat(s2Level,
+ prefixBitCount, suffixBitCount, suffixTableBlockIdOffset, tableEntryBitCount,
+ isAllowedList);
+
+ assertEquals(s2Level, satS2RangeFileFormat.getS2Level());
+ assertEquals(prefixBitCount, satS2RangeFileFormat.getPrefixBitCount());
+ assertEquals(suffixBitCount, satS2RangeFileFormat.getSuffixBitCount());
+ assertEquals(suffixTableBlockIdOffset, satS2RangeFileFormat.getSuffixTableBlockIdOffset());
+ assertEquals(tableEntryBitCount, satS2RangeFileFormat.getTableEntryBitCount());
+ assertEquals(entryRangeLengthBitCount,
+ satS2RangeFileFormat.getTableEntryRangeLengthBitCount());
+
+ // Derived values
+ assertEquals((6 * intPow2(prefixBitCount - 3)) - 1,
+ satS2RangeFileFormat.getMaxPrefixValue());
+ assertEquals(maxValForBits(suffixBitCount), satS2RangeFileFormat.getMaxSuffixValue());
+ assertEquals(tableEntryBitCount / 8, satS2RangeFileFormat.getTableEntryByteCount());
+ assertEquals(maxValForBits(entryRangeLengthBitCount),
+ satS2RangeFileFormat.getTableEntryMaxRangeLengthValue());
+ assertTrue(satS2RangeFileFormat.isAllowedList());
+ }
+
+ @Test
+ public void calculateRangeLength() {
+ int s2Level = 12;
+ int prefixBitCount = 11;
+ int suffixBitCount = 16;
+ int suffixTableBlockIdOffset = 5;
+ int suffixTableEntryBitCount = 24;
+ boolean isAllowedList = false;
+ SatS2RangeFileFormat satS2RangeFileFormat = new SatS2RangeFileFormat(s2Level,
+ prefixBitCount, suffixBitCount, suffixTableBlockIdOffset, suffixTableEntryBitCount,
+ isAllowedList);
+
+ assertEquals(2, satS2RangeFileFormat.calculateRangeLength(
+ cellId(s2Level, 0, 0), cellId(s2Level, 0, 2)));
+ assertEquals(2, satS2RangeFileFormat.calculateRangeLength(
+ cellId(s2Level, 0, 2), cellId(s2Level, 0, 4)));
+
+ int cellsPerFace = intPow2(s2Level * 2);
+ assertEquals(cellsPerFace + 2,
+ satS2RangeFileFormat.calculateRangeLength(
+ cellId(s2Level, 0, 2), cellId(s2Level, 1, 4)));
+ assertFalse(satS2RangeFileFormat.isAllowedList());
+ }
+
+ @Test
+ public void createCellId() {
+ int s2Level = 12;
+ int prefixBitCount = 11;
+ int suffixBitCount = 16;
+ int suffixTableBlockIdOffset = 5;
+ int suffixTableEntryBitCount = 24;
+ boolean isAllowedList = true;
+ SatS2RangeFileFormat satS2RangeFileFormat = new SatS2RangeFileFormat(s2Level,
+ prefixBitCount, suffixBitCount, suffixTableBlockIdOffset, suffixTableEntryBitCount,
+ isAllowedList);
+
+ // Too many bits for prefixValue
+ assertThrows(IllegalArgumentException.class,
+ () -> satS2RangeFileFormat.createCellId(0b1000_00000000, 0b10000000_00000000));
+
+ // Too many bits for suffixValue
+ assertThrows(IllegalArgumentException.class,
+ () -> satS2RangeFileFormat.createCellId(0b1000_00000000, 0b100000000_00000000));
+
+ // Some valid cases.
+ assertEquals(cellId(s2Level, 4, 0),
+ satS2RangeFileFormat.createCellId(0b100_00000000, 0b00000000_00000000));
+ assertEquals(cellId(s2Level, 4, 1),
+ satS2RangeFileFormat.createCellId(0b100_00000000, 0b00000000_00000001));
+
+ assertEquals(cellId(s2Level, 5, intPow2(0)),
+ satS2RangeFileFormat.createCellId(0b101_00000000, 0b00000000_00000001));
+ assertEquals(cellId(s2Level, 5, intPow2(8)),
+ satS2RangeFileFormat.createCellId(0b101_00000000, 0b00000001_00000000));
+ assertEquals(cellId(s2Level, 5, intPow2(16)),
+ satS2RangeFileFormat.createCellId(0b101_00000001, 0b00000000_00000000));
+ assertTrue(satS2RangeFileFormat.isAllowedList());
+ }
+
+ @Test
+ public void extractFaceIdFromPrefix() {
+ int s2Level = 12;
+ int prefixBitCount = 11;
+ int suffixBitCount = 16;
+ int suffixTableBlockIdOffset = 5;
+ int suffixTableEntryBitCount = 24;
+ boolean isAllowedList = true;
+ SatS2RangeFileFormat satS2RangeFileFormat = new SatS2RangeFileFormat(s2Level,
+ prefixBitCount, suffixBitCount, suffixTableBlockIdOffset, suffixTableEntryBitCount,
+ isAllowedList);
+
+ assertEquals(0, satS2RangeFileFormat.extractFaceIdFromPrefix(0b00000000000));
+ assertEquals(5, satS2RangeFileFormat.extractFaceIdFromPrefix(0b10100000000));
+ // We require this (invalid) face ID to work, since this method is used to detect face ID
+ // overflow.
+ assertEquals(6, satS2RangeFileFormat.extractFaceIdFromPrefix(0b11000000000));
+ assertTrue(satS2RangeFileFormat.isAllowedList());
+ }
+
+ @Test
+ public void createSuffixTableValue() {
+ int s2Level = 12;
+ int prefixBitCount = 11;
+ int suffixBitCount = 16;
+ int suffixTableBlockIdOffset = 5;
+ int suffixTableEntryBitCount = 24;
+ boolean isAllowedList = true;
+ SatS2RangeFileFormat satS2RangeFileFormat = new SatS2RangeFileFormat(s2Level,
+ prefixBitCount, suffixBitCount, suffixTableBlockIdOffset, suffixTableEntryBitCount,
+ isAllowedList);
+
+ // Too many bits for rangeLength
+ assertThrows(IllegalArgumentException.class,
+ () -> satS2RangeFileFormat.createSuffixTableValue(0b100000000));
+
+ // Some valid cases.
+ assertEquals(0b10101, satS2RangeFileFormat.createSuffixTableValue(0b10101));
+ assertEquals(0b00000, satS2RangeFileFormat.createSuffixTableValue(0b00000));
+ assertTrue(satS2RangeFileFormat.isAllowedList());
+ }
+
+ private static int maxValForBits(int bits) {
+ return intPow2(bits) - 1;
+ }
+
+ private static int intPow2(int value) {
+ return (int) Math.pow(2, value);
+ }
+}
diff --git a/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SatS2RangeFileReaderTest.java b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SatS2RangeFileReaderTest.java
new file mode 100644
index 0000000..bbfaef7
--- /dev/null
+++ b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SatS2RangeFileReaderTest.java
@@ -0,0 +1,81 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.storage.s2.S2LevelRange;
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+import com.android.telephony.sats2range.read.SatS2RangeFileReader;
+import com.android.telephony.sats2range.utils.TestUtils;
+import com.android.telephony.sats2range.write.SatS2RangeFileWriter;
+
+import org.junit.Test;
+
+import java.io.File;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
+public class SatS2RangeFileReaderTest {
+ @Test
+ public void findEntryByCellId() throws IOException {
+ File file = File.createTempFile("test", ".dat");
+
+ SatS2RangeFileFormat fileFormat;
+ boolean isAllowedList = true;
+ S2LevelRange expectedRange1, expectedRange2, expectedRange3;
+ try (SatS2RangeFileWriter satS2RangeFileWriter = SatS2RangeFileWriter.open(
+ file, TestUtils.createS2RangeFileFormat(isAllowedList))) {
+ fileFormat = satS2RangeFileWriter.getFileFormat();
+
+ // Two ranges that share a prefix.
+ expectedRange1 = new S2LevelRange(
+ TestUtils.createCellId(fileFormat, 1, 1000, 1000),
+ TestUtils.createCellId(fileFormat, 1, 1000, 2000));
+ expectedRange2 = new S2LevelRange(
+ TestUtils.createCellId(fileFormat, 1, 1000, 2000),
+ TestUtils.createCellId(fileFormat, 1, 1000, 3000));
+ // This range has a different prefix, so will be in a different suffix table.
+ expectedRange3 = new S2LevelRange(
+ TestUtils.createCellId(fileFormat, 1, 1001, 1000),
+ TestUtils.createCellId(fileFormat, 1, 1001, 2000));
+
+ List<S2LevelRange> ranges = new ArrayList<>();
+ ranges.add(expectedRange1);
+ ranges.add(expectedRange2);
+ ranges.add(expectedRange3);
+ satS2RangeFileWriter.createSortedSuffixBlocks(ranges.iterator());
+ }
+
+ try (SatS2RangeFileReader satS2RangeFileReader = SatS2RangeFileReader.open(file)) {
+ assertEquals(isAllowedList, satS2RangeFileReader.isAllowedList());
+
+ S2LevelRange range1 = satS2RangeFileReader.findEntryByCellId(
+ TestUtils.createCellId(fileFormat, 1, 1000, 1500));
+ assertEquals(expectedRange1, range1);
+
+ S2LevelRange range2 = satS2RangeFileReader.findEntryByCellId(
+ TestUtils.createCellId(fileFormat, 1, 1000, 2500));
+ assertEquals(expectedRange2, range2);
+
+ S2LevelRange range3 = satS2RangeFileReader.findEntryByCellId(
+ TestUtils.createCellId(fileFormat, 1, 1001, 1500));
+ assertEquals(expectedRange3, range3);
+ }
+ }
+}
diff --git a/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SuffixTableBlockMatcher.java b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SuffixTableBlockMatcher.java
new file mode 100644
index 0000000..483d5f5
--- /dev/null
+++ b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SuffixTableBlockMatcher.java
@@ -0,0 +1,49 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range;
+
+import com.android.telephony.sats2range.read.SuffixTableBlock;
+
+import org.mockito.ArgumentMatcher;
+
+import java.util.Objects;
+
+/** A matcher for {@link SuffixTableBlock} - checks all the various fields and content. */
+public class SuffixTableBlockMatcher implements ArgumentMatcher<SuffixTableBlock> {
+
+ private final SuffixTableBlock mSuffixTableBlock;
+
+ public SuffixTableBlockMatcher(SuffixTableBlock suffixTableBlock) {
+ mSuffixTableBlock = suffixTableBlock;
+ }
+
+ @Override
+ public boolean matches(SuffixTableBlock block) {
+ if (mSuffixTableBlock.getPrefix() != block.getPrefix()
+ || mSuffixTableBlock.getEntryCount() != block.getEntryCount()) {
+ return false;
+ }
+ for (int i = 0; i < mSuffixTableBlock.getEntryCount(); i++) {
+ SuffixTableBlock.Entry expectedEntry = mSuffixTableBlock.getEntryByIndex(i);
+ SuffixTableBlock.Entry actualEntry = block.getEntryByIndex(i);
+ if (!Objects.equals(expectedEntry, actualEntry)) {
+ return false;
+ }
+ }
+ return true;
+ }
+}
diff --git a/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SuffixTableBlockTest.java b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SuffixTableBlockTest.java
new file mode 100644
index 0000000..04b915b
--- /dev/null
+++ b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SuffixTableBlockTest.java
@@ -0,0 +1,311 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range;
+
+import static org.junit.Assert.assertArrayEquals;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertThrows;
+import static org.junit.Assert.assertTrue;
+import static org.mockito.ArgumentMatchers.argThat;
+
+import com.android.storage.block.write.BlockWriter;
+import com.android.storage.s2.S2LevelRange;
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+import com.android.telephony.sats2range.read.SuffixTableBlock;
+import com.android.telephony.sats2range.read.SuffixTableSharedData;
+import com.android.telephony.sats2range.utils.TestUtils;
+import com.android.telephony.sats2range.write.SuffixTableWriter;
+
+import org.junit.Test;
+import org.mockito.InOrder;
+import org.mockito.Mockito;
+
+/** Tests for {@link SuffixTableWriter} and {@link SuffixTableBlock}. */
+public class SuffixTableBlockTest {
+ @Test
+ public void writer_createEmptyBlockWriter() throws Exception {
+ BlockWriter blockWriter = SuffixTableWriter.createEmptyBlockWriter();
+ BlockWriter.ReadBack readBack = blockWriter.close();
+ assertEquals(SatS2RangeFileFormat.BLOCK_TYPE_SUFFIX_TABLE, readBack.getType());
+ assertArrayEquals(new byte[0], readBack.getExtraBytes());
+ assertEquals(0, readBack.getBlockData().getSize());
+ }
+
+ @Test
+ public void writer_createPopulatedBlockWriter_noEntriesThrows() throws Exception {
+ SatS2RangeFileFormat fileFormat = TestUtils.createS2RangeFileFormat(true);
+ assertEquals(13, fileFormat.getPrefixBitCount());
+
+ int tablePrefixValue = 0b0010011_00110100;
+ SuffixTableSharedData suffixTableSharedData = new SuffixTableSharedData(tablePrefixValue);
+
+ SuffixTableWriter suffixTableWriter =
+ SuffixTableWriter.createPopulated(fileFormat, suffixTableSharedData);
+ // IllegalStateException is thrown because there is no entry in the block
+ assertThrows(IllegalStateException.class, suffixTableWriter::close);
+ }
+
+ @Test
+ public void writer_createPopulatedBlockWriter_addRange() throws Exception {
+ SatS2RangeFileFormat fileFormat = TestUtils.createS2RangeFileFormat(true);
+ assertEquals(13, fileFormat.getPrefixBitCount());
+ assertEquals(14, fileFormat.getSuffixBitCount());
+
+ int tablePrefixValue = 0b0010011_00110100;
+ int maxSuffixValue = 0b00111111_11111111;
+ SuffixTableSharedData suffixTableSharedData = new SuffixTableSharedData(tablePrefixValue);
+
+ SuffixTableWriter suffixTableWriter =
+ SuffixTableWriter.createPopulated(fileFormat, suffixTableSharedData);
+
+ long invalidStartCellId = fileFormat.createCellId(tablePrefixValue - 1, 0);
+ long validStartCellId = fileFormat.createCellId(tablePrefixValue, 0);
+ long invalidEndCellId = fileFormat.createCellId(tablePrefixValue + 1, maxSuffixValue);
+ long validEndCellId = fileFormat.createCellId(tablePrefixValue, maxSuffixValue);
+ {
+ S2LevelRange badStartCellId = new S2LevelRange(invalidStartCellId, validEndCellId);
+ assertThrows(IllegalArgumentException.class,
+ () -> suffixTableWriter.addRange(badStartCellId));
+ }
+ {
+ S2LevelRange badEndCellId = new S2LevelRange(validStartCellId, invalidEndCellId);
+ assertThrows(IllegalArgumentException.class,
+ () -> suffixTableWriter.addRange(badEndCellId));
+ }
+ }
+
+ @Test
+ public void writer_createPopulatedBlockWriter_rejectOverlappingRanges() throws Exception {
+ SatS2RangeFileFormat fileFormat = TestUtils.createS2RangeFileFormat(true);
+ assertEquals(13, fileFormat.getPrefixBitCount());
+ assertEquals(14, fileFormat.getSuffixBitCount());
+
+ int tablePrefixValue = 0b0010011_00110100;
+ int maxSuffixValue = 0b00111111_11111111;
+ SuffixTableSharedData suffixTableSharedData = new SuffixTableSharedData(tablePrefixValue);
+
+ SuffixTableWriter suffixTableWriter =
+ SuffixTableWriter.createPopulated(fileFormat, suffixTableSharedData);
+ S2LevelRange suffixTableRange1 = new S2LevelRange(
+ fileFormat.createCellId(tablePrefixValue, 1000),
+ fileFormat.createCellId(tablePrefixValue, 1001));
+ suffixTableWriter.addRange(suffixTableRange1);
+
+ // It's fine to add a range that starts adjacent to the last one.
+ S2LevelRange suffixTableRange2 = new S2LevelRange(
+ fileFormat.createCellId(tablePrefixValue, 1001),
+ fileFormat.createCellId(tablePrefixValue, 1002));
+ suffixTableWriter.addRange(suffixTableRange2);
+
+ // IllegalArgumentException is thrown because suffixTableRange2 already exists
+ assertThrows(IllegalArgumentException.class,
+ () -> suffixTableWriter.addRange(suffixTableRange2));
+
+ // Try similar checks at the top end of the table.
+ S2LevelRange suffixTableRange3 = new S2LevelRange(
+ fileFormat.createCellId(tablePrefixValue, maxSuffixValue - 1),
+ fileFormat.createCellId(tablePrefixValue, maxSuffixValue));
+ suffixTableWriter.addRange(suffixTableRange3);
+
+ // IllegalArgumentException is thrown because ranges already exist
+ assertThrows(IllegalArgumentException.class,
+ () -> suffixTableWriter.addRange(suffixTableRange1));
+ assertThrows(IllegalArgumentException.class,
+ () -> suffixTableWriter.addRange(suffixTableRange2));
+ assertThrows(IllegalArgumentException.class,
+ () -> suffixTableWriter.addRange(suffixTableRange3));
+
+ // Now "complete" the table: there can be no entry after this one.
+ S2LevelRange suffixTableRange4 = new S2LevelRange(
+ fileFormat.createCellId(tablePrefixValue, maxSuffixValue),
+ fileFormat.createCellId(tablePrefixValue + 1, 0));
+ suffixTableWriter.addRange(suffixTableRange4);
+
+ assertThrows(IllegalArgumentException.class,
+ () -> suffixTableWriter.addRange(suffixTableRange4));
+
+ assertThrows(IllegalArgumentException.class,
+ () -> suffixTableWriter.addRange(suffixTableRange1));
+ assertThrows(IllegalArgumentException.class,
+ () -> suffixTableWriter.addRange(suffixTableRange2));
+ assertThrows(IllegalArgumentException.class,
+ () -> suffixTableWriter.addRange(suffixTableRange3));
+ assertThrows(IllegalArgumentException.class,
+ () -> suffixTableWriter.addRange(suffixTableRange4));
+ }
+
+ @Test
+ public void suffixTableBlock_empty() {
+ SatS2RangeFileFormat fileFormat = TestUtils.createS2RangeFileFormat(true);
+ assertEquals(13, fileFormat.getPrefixBitCount());
+ int tablePrefix = 0b10011_00110100;
+
+ SuffixTableBlock suffixTableBlock = SuffixTableBlock.createEmpty(fileFormat, tablePrefix);
+ assertEquals(tablePrefix, suffixTableBlock.getPrefix());
+ assertNull(suffixTableBlock.findEntryByCellId(fileFormat.createCellId(tablePrefix, 1)));
+ assertEquals(0, suffixTableBlock.getEntryCount());
+ assertThrows(IndexOutOfBoundsException.class,
+ () -> suffixTableBlock.getEntryByIndex(0));
+ assertThrows(IndexOutOfBoundsException.class,
+ () -> suffixTableBlock.getEntryByIndex(1));
+ }
+
+ @Test
+ public void suffixTableBlock_populated_findEntryByCellId() throws Exception {
+ SatS2RangeFileFormat fileFormat = TestUtils.createS2RangeFileFormat(true);
+ assertEquals(13, fileFormat.getPrefixBitCount());
+ assertEquals(14, fileFormat.getSuffixBitCount());
+
+ int tablePrefix = 0b10011_00110100;
+ int maxSuffix = 0b111111_11111111;
+ SuffixTableSharedData suffixTableSharedData = new SuffixTableSharedData(tablePrefix);
+
+ SuffixTableWriter suffixTableWriter =
+ SuffixTableWriter.createPopulated(fileFormat, suffixTableSharedData);
+
+ long entry1StartCellId = fileFormat.createCellId(tablePrefix, 1000);
+ long entry1EndCellId = fileFormat.createCellId(tablePrefix, 2000);
+ S2LevelRange entry1 = new S2LevelRange(entry1StartCellId, entry1EndCellId);
+ suffixTableWriter.addRange(entry1);
+
+ long entry2StartCellId = fileFormat.createCellId(tablePrefix, 2000);
+ long entry2EndCellId = fileFormat.createCellId(tablePrefix, 3000);
+ S2LevelRange entry2 = new S2LevelRange(entry2StartCellId, entry2EndCellId);
+ suffixTableWriter.addRange(entry2);
+
+ // There is a deliberate gap here between entry2 and entry3.
+ long entry3StartCellId = fileFormat.createCellId(tablePrefix, 4000);
+ long entry3EndCellId = fileFormat.createCellId(tablePrefix, 5000);
+ S2LevelRange entry3 = new S2LevelRange(entry3StartCellId, entry3EndCellId);
+ suffixTableWriter.addRange(entry3);
+
+ long entry4StartCellId = fileFormat.createCellId(tablePrefix, maxSuffix - 999);
+ long entry4EndCellId = fileFormat.createCellId(tablePrefix + 1, 0);
+ S2LevelRange entry4 = new S2LevelRange(entry4StartCellId, entry4EndCellId);
+ suffixTableWriter.addRange(entry4);
+
+ BlockWriter.ReadBack blockReadback = suffixTableWriter.close();
+ SuffixTableBlock suffixTableBlock =
+ SuffixTableBlock.createPopulated(fileFormat, blockReadback.getBlockData());
+ assertEquals(tablePrefix, suffixTableBlock.getPrefix());
+
+ assertNull(findEntryByCellId(fileFormat, suffixTableBlock, tablePrefix, 999));
+ assertEquals(entry1, findEntryByCellId(fileFormat, suffixTableBlock, tablePrefix, 1000));
+ assertEquals(entry1, findEntryByCellId(fileFormat, suffixTableBlock, tablePrefix, 1001));
+ assertEquals(entry1, findEntryByCellId(fileFormat, suffixTableBlock, tablePrefix, 1999));
+ assertEquals(entry2, findEntryByCellId(fileFormat, suffixTableBlock, tablePrefix, 2000));
+ assertEquals(entry2, findEntryByCellId(fileFormat, suffixTableBlock, tablePrefix, 2001));
+ assertEquals(entry2, findEntryByCellId(fileFormat, suffixTableBlock, tablePrefix, 2999));
+ assertNull(findEntryByCellId(fileFormat, suffixTableBlock, tablePrefix, 3000));
+ assertNull(findEntryByCellId(fileFormat, suffixTableBlock, tablePrefix, 3999));
+ assertEquals(entry3, findEntryByCellId(fileFormat, suffixTableBlock, tablePrefix, 4000));
+ assertEquals(entry3, findEntryByCellId(fileFormat, suffixTableBlock, tablePrefix, 4999));
+ assertNull(findEntryByCellId(fileFormat, suffixTableBlock, tablePrefix, maxSuffix - 1000));
+ assertEquals(
+ entry4,
+ findEntryByCellId(fileFormat, suffixTableBlock, tablePrefix, maxSuffix - 999));
+ assertEquals(
+ entry4,
+ findEntryByCellId(fileFormat, suffixTableBlock, tablePrefix, maxSuffix));
+
+ assertEquals(4, suffixTableBlock.getEntryCount());
+ assertThrows(IndexOutOfBoundsException.class,
+ () -> suffixTableBlock.getEntryByIndex(-1));
+ assertThrows(IndexOutOfBoundsException.class,
+ () -> suffixTableBlock.getEntryByIndex(4));
+
+ assertEquals(entry1, suffixTableBlock.getEntryByIndex(0).getSuffixTableRange());
+ assertEquals(entry2, suffixTableBlock.getEntryByIndex(1).getSuffixTableRange());
+ assertEquals(entry3, suffixTableBlock.getEntryByIndex(2).getSuffixTableRange());
+ assertEquals(entry4, suffixTableBlock.getEntryByIndex(3).getSuffixTableRange());
+ }
+
+ @Test
+ public void suffixTableBlock_populated_findEntryByCellId_cellIdOutOfRange() throws Exception {
+ SatS2RangeFileFormat fileFormat = TestUtils.createS2RangeFileFormat(true);
+
+ int tablePrefix = 0b10011_00110100;
+ assertEquals(13, fileFormat.getPrefixBitCount());
+
+ int tzIdSetBankId = 5;
+ assertTrue(tzIdSetBankId <= fileFormat.getMaxPrefixValue());
+
+ SuffixTableSharedData suffixTableSharedData = new SuffixTableSharedData(tablePrefix);
+
+ SuffixTableWriter suffixTableWriter =
+ SuffixTableWriter.createPopulated(fileFormat, suffixTableSharedData);
+ long entry1StartCellId = fileFormat.createCellId(tablePrefix, 1000);
+ long entry1EndCellId = fileFormat.createCellId(tablePrefix, 2000);
+ S2LevelRange entry1 = new S2LevelRange(entry1StartCellId, entry1EndCellId);
+ suffixTableWriter.addRange(entry1);
+ BlockWriter.ReadBack blockReadback = suffixTableWriter.close();
+
+ SuffixTableBlock suffixTableBlock =
+ SuffixTableBlock.createPopulated(fileFormat, blockReadback.getBlockData());
+
+ assertThrows(IllegalArgumentException.class, () -> suffixTableBlock.findEntryByCellId(
+ fileFormat.createCellId(tablePrefix - 1, 0)));
+ assertThrows(IllegalArgumentException.class, () -> suffixTableBlock.findEntryByCellId(
+ fileFormat.createCellId(tablePrefix + 1, 0)));
+ }
+
+ @Test
+ public void suffixTableBlock_visit() throws Exception {
+ SatS2RangeFileFormat fileFormat = TestUtils.createS2RangeFileFormat(true);
+
+ int tablePrefix = 0b10011_00110100;
+ assertEquals(13, fileFormat.getPrefixBitCount());
+
+ SuffixTableSharedData sharedData = new SuffixTableSharedData(tablePrefix);
+
+ SuffixTableWriter suffixTableWriter =
+ SuffixTableWriter.createPopulated(fileFormat, sharedData);
+
+ S2LevelRange entry1 = new S2LevelRange(
+ fileFormat.createCellId(tablePrefix, 1001),
+ fileFormat.createCellId(tablePrefix, 1101));
+ suffixTableWriter.addRange(entry1);
+
+ S2LevelRange entry2 = new S2LevelRange(
+ fileFormat.createCellId(tablePrefix, 2001),
+ fileFormat.createCellId(tablePrefix, 2101));
+ suffixTableWriter.addRange(entry2);
+
+ BlockWriter.ReadBack readBack = suffixTableWriter.close();
+
+ // Read the data back and confirm it matches what we expected.
+ SuffixTableBlock suffixTableBlock =
+ SuffixTableBlock.createPopulated(fileFormat, readBack.getBlockData());
+ SuffixTableBlock.SuffixTableBlockVisitor mockVisitor =
+ Mockito.mock(SuffixTableBlock.SuffixTableBlockVisitor.class);
+
+ suffixTableBlock.visit(mockVisitor);
+
+ InOrder inOrder = Mockito.inOrder(mockVisitor);
+ inOrder.verify(mockVisitor).begin();
+ inOrder.verify(mockVisitor).visit(argThat(new SuffixTableBlockMatcher(suffixTableBlock)));
+ inOrder.verify(mockVisitor).end();
+ }
+
+ private S2LevelRange findEntryByCellId(SatS2RangeFileFormat fileFormat,
+ SuffixTableBlock suffixTableBlock, int prefix, int suffix) {
+ long cellId = fileFormat.createCellId(prefix, suffix);
+ SuffixTableBlock.Entry entry = suffixTableBlock.findEntryByCellId(cellId);
+ return entry == null ? null : entry.getSuffixTableRange();
+ }
+}
diff --git a/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SuffixTableExtraInfoTest.java b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SuffixTableExtraInfoTest.java
new file mode 100644
index 0000000..f992ae7
--- /dev/null
+++ b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SuffixTableExtraInfoTest.java
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.storage.block.read.BlockInfo;
+import com.android.storage.block.write.BlockWriter;
+import com.android.storage.s2.S2LevelRange;
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+import com.android.telephony.sats2range.read.SuffixTableExtraInfo;
+import com.android.telephony.sats2range.read.SuffixTableSharedData;
+import com.android.telephony.sats2range.utils.TestUtils;
+import com.android.telephony.sats2range.write.SuffixTableWriter;
+
+import org.junit.Test;
+public class SuffixTableExtraInfoTest {
+
+ @Test
+ public void create_emptyBlock() throws Exception {
+ // Generate a real suffix table block info and an empty block.
+ SatS2RangeFileFormat fileFormat = TestUtils.createS2RangeFileFormat(true);
+ BlockWriter emptyBlockWriter =
+ SuffixTableWriter.createEmptyBlockWriter();
+ BlockWriter.ReadBack readBack = emptyBlockWriter.close();
+
+ // Read back the block info.
+ BlockInfo blockInfo = createBlockInfo(readBack);
+
+ SuffixTableExtraInfo extraInfo = SuffixTableExtraInfo.create(fileFormat, blockInfo);
+ assertEquals(0, extraInfo.getEntryCount());
+ }
+
+ @Test
+ public void create_nonEmptyBlock() throws Exception {
+ // Generate a real suffix table block info and block containing some elements.
+ SatS2RangeFileFormat fileFormat = TestUtils.createS2RangeFileFormat(true);
+ SuffixTableSharedData suffixTableSharedData = createSuffixTableSharedData();
+ SuffixTableWriter suffixTableWriter =
+ SuffixTableWriter.createPopulated(fileFormat, suffixTableSharedData);
+
+ int tablePrefix = suffixTableSharedData.getTablePrefix();
+ S2LevelRange range1 = new S2LevelRange(
+ fileFormat.createCellId(tablePrefix, 1000),
+ fileFormat.createCellId(tablePrefix, 1001));
+ S2LevelRange range2 = new S2LevelRange(
+ fileFormat.createCellId(tablePrefix, 1002),
+ fileFormat.createCellId(tablePrefix, 1003));
+ S2LevelRange range3 = new S2LevelRange(
+ fileFormat.createCellId(tablePrefix, 1004),
+ fileFormat.createCellId(tablePrefix, 1005));
+
+ suffixTableWriter.addRange(range1);
+ suffixTableWriter.addRange(range2);
+ suffixTableWriter.addRange(range3);
+ BlockWriter.ReadBack readBack = suffixTableWriter.close();
+
+ // Read back the block info.
+ BlockInfo blockInfo = createBlockInfo(readBack);
+
+ SuffixTableExtraInfo extraInfo = SuffixTableExtraInfo.create(fileFormat, blockInfo);
+ assertEquals(3, extraInfo.getEntryCount());
+ }
+
+ private static SuffixTableSharedData createSuffixTableSharedData() {
+ int arbitraryPrefixValue = 1111;
+ return new SuffixTableSharedData(arbitraryPrefixValue);
+ }
+
+ /** Creates a BlockInfo for a written block. */
+ private static BlockInfo createBlockInfo(BlockWriter.ReadBack readBack) {
+ int arbitraryBlockId = 2222;
+ long arbitraryByteOffset = 12345L;
+ return new BlockInfo(
+ arbitraryBlockId, readBack.getType(), arbitraryByteOffset,
+ readBack.getBlockData().getSize(), readBack.getExtraBytes());
+ }
+}
diff --git a/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SuffixTableSharedDataTest.java b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SuffixTableSharedDataTest.java
new file mode 100644
index 0000000..2baefa9
--- /dev/null
+++ b/utils/satellite/s2storage/src/test/java/com/android/telephony/sats2range/SuffixTableSharedDataTest.java
@@ -0,0 +1,37 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.telephony.sats2range.read.SuffixTableSharedData;
+import com.android.telephony.sats2range.write.SuffixTableSharedDataWriter;
+
+import org.junit.Test;
+
+/** Tests for {@link SuffixTableSharedData} and {@link SuffixTableSharedDataWriter}. */
+public class SuffixTableSharedDataTest {
+ @Test
+ public void testSuffixTableSharedData() {
+ int prefix = 321;
+ SuffixTableSharedData sharedData = new SuffixTableSharedData(prefix);
+ byte[] bytes = SuffixTableSharedDataWriter.toBytes(sharedData);
+
+ assertEquals(sharedData, SuffixTableSharedData.fromBytes(bytes));
+ }
+}
+
diff --git a/utils/satellite/s2storage/src/testutils/java/com/android/telephony/sats2range/testutils/TestUtils.java b/utils/satellite/s2storage/src/testutils/java/com/android/telephony/sats2range/testutils/TestUtils.java
new file mode 100644
index 0000000..4b8a026
--- /dev/null
+++ b/utils/satellite/s2storage/src/testutils/java/com/android/telephony/sats2range/testutils/TestUtils.java
@@ -0,0 +1,144 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range.utils;
+
+import static com.android.storage.s2.S2Support.FACE_BIT_COUNT;
+
+import static org.junit.Assert.assertFalse;
+
+import com.android.storage.util.BitwiseUtils;
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+
+import java.io.File;
+import java.io.IOException;
+import java.io.PrintStream;
+import java.nio.file.FileVisitResult;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.nio.file.SimpleFileVisitor;
+import java.nio.file.attribute.BasicFileAttributes;
+
+/** A utility class for satellite tests */
+public class TestUtils {
+ public static final int TEST_S2_LEVEL = 12;
+
+ /** Returns a valid {@link SatS2RangeFileFormat}. */
+ public static SatS2RangeFileFormat createS2RangeFileFormat(boolean isAllowedList) {
+ int dataS2Level = TEST_S2_LEVEL;
+ int faceIdBits = 3;
+ int bitCountPerLevel = 2;
+ int s2LevelBitCount = (dataS2Level * bitCountPerLevel) + faceIdBits;
+ int prefixLevel = 5;
+ int prefixBitCount = faceIdBits + (prefixLevel * bitCountPerLevel);
+ int suffixBitCount = s2LevelBitCount - prefixBitCount;
+ int suffixTableEntryBitCount = 4 * Byte.SIZE;
+ int suffixTableBlockIdOffset = 5;
+ return new SatS2RangeFileFormat(dataS2Level, prefixBitCount, suffixBitCount,
+ suffixTableBlockIdOffset, suffixTableEntryBitCount, isAllowedList);
+ }
+
+ /** Create an S2 cell ID */
+ public static long createCellId(
+ SatS2RangeFileFormat fileFormat, int faceId, int otherPrefixBits, int suffixBits) {
+ int prefixBitCount = fileFormat.getPrefixBitCount();
+ int otherPrefixBitsCount = prefixBitCount - FACE_BIT_COUNT;
+ int maxOtherPrefixBits = (int) BitwiseUtils.getLowBitsMask(otherPrefixBitsCount);
+ if (otherPrefixBits > maxOtherPrefixBits) {
+ throw new IllegalArgumentException("otherPrefixBits=" + otherPrefixBits
+ + " (" + Integer.toBinaryString(otherPrefixBits) + ")"
+ + " has more bits than otherPrefixBitsCount=" + otherPrefixBitsCount
+ + " allows");
+ }
+
+ int prefixValue = faceId;
+ prefixValue <<= otherPrefixBitsCount;
+ prefixValue |= otherPrefixBits;
+
+ int suffixBitCount = fileFormat.getSuffixBitCount();
+ if (suffixBits > BitwiseUtils.getLowBitsMask(suffixBitCount)) {
+ throw new IllegalArgumentException(
+ "suffixBits=" + suffixBits + " (" + Integer.toBinaryString(suffixBits)
+ + ") has more bits than " + suffixBitCount + " bits allows");
+ }
+ return fileFormat.createCellId(prefixValue, suffixBits);
+ }
+
+ /** Create a temporary directory */
+ public static Path createTempDir(Class<?> testClass) throws IOException {
+ return Files.createTempDirectory(testClass.getSimpleName());
+ }
+
+ /** Delete a directory */
+ public static void deleteDirectory(Path dir) throws IOException {
+ Files.walkFileTree(dir, new SimpleFileVisitor<>() {
+ @Override
+ public FileVisitResult visitFile(Path path, BasicFileAttributes basicFileAttributes)
+ throws IOException {
+ Files.deleteIfExists(path);
+ return FileVisitResult.CONTINUE;
+ }
+
+ @Override
+ public FileVisitResult postVisitDirectory(Path path, IOException e) throws IOException {
+ Files.delete(path);
+ return FileVisitResult.CONTINUE;
+ }
+ });
+ assertFalse(Files.exists(dir));
+ }
+
+ /** Create a valid test satellite S2 cell file */
+ public static void createValidTestS2CellFile(
+ File outputFile, SatS2RangeFileFormat fileFormat) throws Exception {
+ try (PrintStream printer = new PrintStream(outputFile)) {
+ // Range 1
+ for (int suffix = 1000; suffix < 2000; suffix++) {
+ printer.println(String.valueOf(fileFormat.createCellId(0b100_11111111, suffix)));
+ }
+
+ // Range 2
+ for (int suffix = 2001; suffix < 3000; suffix++) {
+ printer.println(String.valueOf(fileFormat.createCellId(0b100_11111111, suffix)));
+ }
+
+ // Range 3
+ for (int suffix = 1000; suffix < 2000; suffix++) {
+ printer.println(String.valueOf(fileFormat.createCellId(0b101_11111111, suffix)));
+ }
+ printer.print(String.valueOf(fileFormat.createCellId(0b101_11111111, 2000)));
+
+ printer.close();
+ }
+ }
+
+ /** Create a invalid test satellite S2 cell file */
+ public static void createInvalidTestS2CellFile(
+ File outputFile, SatS2RangeFileFormat fileFormat) throws Exception {
+ try (PrintStream printer = new PrintStream(outputFile)) {
+ // Valid line
+ printer.println(String.valueOf(fileFormat.createCellId(0b100_11111111, 100)));
+
+ // Invalid line
+ printer.print("Invalid line");
+
+ // Another valid line
+ printer.println(String.valueOf(fileFormat.createCellId(0b100_11111111, 200)));
+
+ printer.close();
+ }
+ }
+}
diff --git a/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/HeaderBlockWriter.java b/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/HeaderBlockWriter.java
new file mode 100644
index 0000000..d4e9310
--- /dev/null
+++ b/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/HeaderBlockWriter.java
@@ -0,0 +1,95 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range.write;
+
+import com.android.storage.block.read.BlockData;
+import com.android.storage.block.write.BlockWriter;
+import com.android.storage.io.write.TypedOutputStream;
+import com.android.telephony.sats2range.read.HeaderBlock;
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+
+import java.io.File;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.nio.MappedByteBuffer;
+import java.nio.channels.FileChannel;
+import java.nio.file.StandardOpenOption;
+
+/** A {@link BlockWriter} that can generate a satellite S2 data file header block. */
+public final class HeaderBlockWriter implements BlockWriter {
+
+ private static final byte[] EMPTY_BYTE_ARRAY = new byte[0];
+
+ private final File mFile;
+
+ private final SatS2RangeFileFormat mFileFormat;
+
+ private boolean mIsOpen = true;
+
+ private HeaderBlockWriter(SatS2RangeFileFormat fileFormat, File file) {
+ mFileFormat = fileFormat;
+ mFile = file;
+ }
+
+ /** Creates a new {@link HeaderBlockWriter}. */
+ public static HeaderBlockWriter create(SatS2RangeFileFormat fileFormat) throws IOException {
+ return new HeaderBlockWriter(fileFormat, File.createTempFile("header", ".bin"));
+ }
+
+ @Override
+ public ReadBack close() throws IOException {
+ checkIsOpen();
+ mIsOpen = false;
+
+ try (TypedOutputStream tos = new TypedOutputStream(new FileOutputStream(mFile))) {
+ tos.writeUnsignedByte(mFileFormat.getS2Level());
+ tos.writeUnsignedByte(mFileFormat.getPrefixBitCount());
+ tos.writeUnsignedByte(mFileFormat.getSuffixBitCount());
+ tos.writeUnsignedByte(mFileFormat.getTableEntryBitCount());
+ tos.writeUnsignedByte(mFileFormat.getSuffixTableBlockIdOffset());
+ tos.writeUnsignedByte(mFileFormat.isAllowedList()
+ ? HeaderBlock.TRUE : HeaderBlock.FALSE);
+ }
+
+ FileChannel fileChannel = FileChannel.open(mFile.toPath(), StandardOpenOption.READ);
+ MappedByteBuffer map = fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, mFile.length());
+ fileChannel.close();
+ BlockData blockData = new BlockData(map);
+ return new ReadBack() {
+ @Override
+ public byte[] getExtraBytes() {
+ return EMPTY_BYTE_ARRAY;
+ }
+
+ @Override
+ public int getType() {
+ return SatS2RangeFileFormat.BLOCK_TYPE_HEADER;
+ }
+
+ @Override
+ public BlockData getBlockData() {
+ return blockData;
+ }
+ };
+ }
+
+ private void checkIsOpen() {
+ if (!mIsOpen) {
+ throw new IllegalStateException("Writer is closed.");
+ }
+ }
+}
diff --git a/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/PushBackIterator.java b/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/PushBackIterator.java
new file mode 100644
index 0000000..7bc375e
--- /dev/null
+++ b/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/PushBackIterator.java
@@ -0,0 +1,56 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range.write;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+
+/**
+ * An iterator that can have elements pushed back onto it. {@link #remove()} is not supported.
+ *
+ * @param <E> The type of the element returned by this iterator
+ */
+public final class PushBackIterator<E> implements Iterator<E> {
+
+ private final ArrayList<E> mPushBackStack = new ArrayList<>();
+
+ private final Iterator<E> mIterator;
+
+ public PushBackIterator(Iterator<E> iterator) {
+ mIterator = iterator;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return !mPushBackStack.isEmpty() || mIterator.hasNext();
+ }
+
+ @Override
+ public E next() {
+ if (!mPushBackStack.isEmpty()) {
+ return mPushBackStack.remove(mPushBackStack.size() - 1);
+ }
+ return mIterator.next();
+ }
+
+ /**
+ * Pushes the element to the front of the iterator again.
+ */
+ public void pushBack(E element) {
+ mPushBackStack.add(element);
+ }
+}
diff --git a/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/SatS2RangeFileWriter.java b/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/SatS2RangeFileWriter.java
new file mode 100644
index 0000000..9b3c20e
--- /dev/null
+++ b/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/SatS2RangeFileWriter.java
@@ -0,0 +1,237 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range.write;
+
+import com.android.storage.block.write.BlockFileWriter;
+import com.android.storage.block.write.BlockWriter;
+import com.android.storage.block.write.EmptyBlockWriter;
+import com.android.storage.s2.S2LevelRange;
+import com.android.storage.s2.S2Support;
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+import com.android.telephony.sats2range.read.SuffixTableSharedData;
+
+import java.io.File;
+import java.io.IOException;
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Deque;
+import java.util.Iterator;
+import java.util.List;
+
+/** Writes a satellite S2 data file. */
+public final class SatS2RangeFileWriter implements AutoCloseable {
+
+ private final HeaderBlockWriter mHeaderBlockWriter;
+
+ private final List<BlockWriter> mSuffixTableBlockWriters = new ArrayList<>();
+
+ private final BlockFileWriter mBlockFileWriter;
+
+ private final SatS2RangeFileFormat mFileFormat;
+
+ private SatS2RangeFileWriter(SatS2RangeFileFormat fileFormat, BlockFileWriter blockFileWriter)
+ throws IOException {
+ mBlockFileWriter = blockFileWriter;
+ mFileFormat = fileFormat;
+
+ mHeaderBlockWriter = HeaderBlockWriter.create(fileFormat);
+ }
+
+ /** Opens a file for writing with the specified format. */
+ public static SatS2RangeFileWriter open(File outFile, SatS2RangeFileFormat fileFormat)
+ throws IOException {
+ BlockFileWriter writer = BlockFileWriter.open(
+ SatS2RangeFileFormat.MAGIC, SatS2RangeFileFormat.VERSION, outFile);
+ return new SatS2RangeFileWriter(fileFormat, writer);
+ }
+
+ /**
+ * Group the sorted ranges into contiguous suffix blocks. Big ranges might get split as
+ * needed to fit them into suffix blocks. The ranges must be of the expected S2 level
+ * and ordered by cell ID.
+ */
+ public void createSortedSuffixBlocks(Iterator<S2LevelRange> ranges) throws IOException {
+ PushBackIterator<S2LevelRange> pushBackIterator = new PushBackIterator<>(ranges);
+
+ // For each prefix value, collect all the ranges that match.
+ for (int currentPrefix = 0;
+ currentPrefix <= mFileFormat.getMaxPrefixValue();
+ currentPrefix++) {
+
+ // Step 1:
+ // populate samePrefixRanges, which holds ranges that have a prefix of currentPrefix.
+ List<S2LevelRange> samePrefixRanges =
+ collectSamePrefixRanges(pushBackIterator, currentPrefix);
+
+ // Step 2: Write samePrefixRanges to a suffix table.
+ BlockWriter blockWriter = writeSamePrefixRanges(currentPrefix, samePrefixRanges);
+ mSuffixTableBlockWriters.add(blockWriter);
+ }
+
+ // At this point there should be no data left.
+ if (pushBackIterator.hasNext()) {
+ throw new IllegalStateException("Unexpected ranges left at the end.");
+ }
+ }
+
+ private List<S2LevelRange> collectSamePrefixRanges(
+ PushBackIterator<S2LevelRange> pushBackIterator, int currentPrefix) {
+ List<S2LevelRange> samePrefixRanges = new ArrayList<>();
+ while (pushBackIterator.hasNext()) {
+ S2LevelRange currentRange = pushBackIterator.next();
+
+ long startCellId = currentRange.getStartCellId();
+ if (mFileFormat.getS2Level() != S2Support.getS2Level(startCellId)) {
+ throw new IllegalArgumentException(
+ "Input data level does not match file format level");
+ }
+ int startCellPrefix = mFileFormat.extractPrefixValueFromCellId(startCellId);
+ if (startCellPrefix != currentPrefix) {
+ if (startCellPrefix < currentPrefix) {
+ throw new IllegalStateException("Prefix out of order:"
+ + " currentPrefixValue=" + currentPrefix
+ + " startCellPrefixValue=" + startCellPrefix);
+ }
+ // The next range is for a later prefix. Put it back and move to step 2.
+ pushBackIterator.pushBack(currentRange);
+ break;
+ }
+
+ long endCellId = currentRange.getEndCellId();
+ if (mFileFormat.getS2Level() != S2Support.getS2Level(endCellId)) {
+ throw new IllegalArgumentException("endCellId in range " + currentRange
+ + " has the wrong S2 level");
+ }
+
+ // Split ranges if they span a prefix.
+ int endCellPrefixValue = mFileFormat.extractPrefixValueFromCellId(endCellId);
+ if (startCellPrefix != endCellPrefixValue) {
+ // Create a range for the current prefix.
+ {
+ long newEndCellId = mFileFormat.createCellId(startCellPrefix + 1, 0);
+ S2LevelRange satS2Range = new S2LevelRange(startCellId, newEndCellId);
+ samePrefixRanges.add(satS2Range);
+ }
+
+ Deque<S2LevelRange> otherRanges = new ArrayDeque<>();
+ // Intermediate prefixes.
+ startCellPrefix = startCellPrefix + 1;
+ while (startCellPrefix != endCellPrefixValue) {
+ long newStartCellId = mFileFormat.createCellId(startCellPrefix, 0);
+ long newEndCellId = mFileFormat.createCellId(startCellPrefix + 1, 0);
+ S2LevelRange satS2Range = new S2LevelRange(newStartCellId, newEndCellId);
+ otherRanges.add(satS2Range);
+ startCellPrefix++;
+ }
+
+ // Final prefix.
+ {
+ long newStartCellId = mFileFormat.createCellId(endCellPrefixValue, 0);
+ if (newStartCellId != endCellId) {
+ S2LevelRange satS2Range = new S2LevelRange(newStartCellId, endCellId);
+ otherRanges.add(satS2Range);
+ }
+ }
+
+ // Push back the ranges in reverse order so they come back out in sorted order.
+ while (!otherRanges.isEmpty()) {
+ pushBackIterator.pushBack(otherRanges.removeLast());
+ }
+ break;
+ } else {
+ samePrefixRanges.add(currentRange);
+ }
+ }
+ return samePrefixRanges;
+ }
+
+ private BlockWriter writeSamePrefixRanges(
+ int currentPrefix, List<S2LevelRange> samePrefixRanges) throws IOException {
+ BlockWriter blockWriter;
+ if (samePrefixRanges.size() == 0) {
+ // Add an empty block.
+ blockWriter = SuffixTableWriter.createEmptyBlockWriter();
+ } else {
+ // Create a suffix table block.
+ SuffixTableSharedData sharedData = new SuffixTableSharedData(currentPrefix);
+ SuffixTableWriter suffixTableWriter =
+ SuffixTableWriter.createPopulated(mFileFormat, sharedData);
+ S2LevelRange lastRange = null;
+ for (S2LevelRange currentRange : samePrefixRanges) {
+ // Validate ranges don't overlap.
+ if (lastRange != null) {
+ if (lastRange.overlaps(currentRange)) {
+ throw new IllegalStateException("lastRange=" + lastRange + " overlaps"
+ + " currentRange=" + currentRange);
+ }
+ }
+ lastRange = currentRange;
+
+ // Split the range so it fits.
+ final int maxRangeLength = mFileFormat.getTableEntryMaxRangeLengthValue();
+ long startCellId = currentRange.getStartCellId();
+ long endCellId = currentRange.getEndCellId();
+ int rangeLength = mFileFormat.calculateRangeLength(startCellId, endCellId);
+ while (rangeLength > maxRangeLength) {
+ long newEndCellId = S2Support.offsetCellId(startCellId, maxRangeLength);
+ S2LevelRange suffixTableRange = new S2LevelRange(startCellId, newEndCellId);
+ suffixTableWriter.addRange(suffixTableRange);
+ startCellId = newEndCellId;
+ rangeLength = mFileFormat.calculateRangeLength(startCellId, endCellId);
+ }
+ S2LevelRange suffixTableRange = new S2LevelRange(startCellId, endCellId);
+ suffixTableWriter.addRange(suffixTableRange);
+ }
+ blockWriter = suffixTableWriter;
+ }
+ return blockWriter;
+ }
+
+ @Override
+ public void close() throws IOException {
+ try {
+ BlockWriter.ReadBack headerReadBack = mHeaderBlockWriter.close();
+ mBlockFileWriter.addBlock(headerReadBack.getType(), headerReadBack.getExtraBytes(),
+ headerReadBack.getBlockData());
+
+ // Add empty blocks padding.
+ EmptyBlockWriter emptyBlockWriterHelper =
+ new EmptyBlockWriter(SatS2RangeFileFormat.BLOCK_TYPE_PADDING);
+ BlockWriter.ReadBack emptyBlockReadBack = emptyBlockWriterHelper.close();
+ for (int i = 0; i < mFileFormat.getSuffixTableBlockIdOffset() - 1; i++) {
+ mBlockFileWriter.addBlock(
+ emptyBlockReadBack.getType(), emptyBlockReadBack.getExtraBytes(),
+ emptyBlockReadBack.getBlockData());
+ }
+
+ // Add the suffix tables.
+ for (BlockWriter blockWriter : mSuffixTableBlockWriters) {
+ BlockWriter.ReadBack readBack = blockWriter.close();
+
+ mBlockFileWriter.addBlock(readBack.getType(), readBack.getExtraBytes(),
+ readBack.getBlockData());
+ }
+ } finally {
+ mBlockFileWriter.close();
+ }
+ }
+
+ /** Returns the{@link SatS2RangeFileFormat} for the file being written. */
+ public SatS2RangeFileFormat getFileFormat() {
+ return mFileFormat;
+ }
+}
diff --git a/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/SuffixTableSharedDataWriter.java b/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/SuffixTableSharedDataWriter.java
new file mode 100644
index 0000000..5499148
--- /dev/null
+++ b/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/SuffixTableSharedDataWriter.java
@@ -0,0 +1,45 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range.write;
+
+import com.android.storage.io.write.TypedOutputStream;
+import com.android.telephony.sats2range.read.SuffixTableSharedData;
+
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+
+/**
+ * Converts a {@link SuffixTableSharedData} to a byte[] for writing.
+ * See also {@link SuffixTableSharedData#fromBytes(byte[])}.
+ */
+public final class SuffixTableSharedDataWriter {
+
+ private SuffixTableSharedDataWriter() {
+ }
+
+ /** Returns the byte[] for the supplied {@link SuffixTableSharedData} */
+ public static byte[] toBytes(SuffixTableSharedData suffixTableSharedData) {
+ try (ByteArrayOutputStream baos = new ByteArrayOutputStream();
+ TypedOutputStream tos = new TypedOutputStream(baos)) {
+ tos.writeInt(suffixTableSharedData.getTablePrefix());
+ tos.flush();
+ return baos.toByteArray();
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ }
+}
diff --git a/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/SuffixTableWriter.java b/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/SuffixTableWriter.java
new file mode 100644
index 0000000..d9e4575
--- /dev/null
+++ b/utils/satellite/s2storage/src/write/java/com/android/telephony/sats2range/write/SuffixTableWriter.java
@@ -0,0 +1,202 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.sats2range.write;
+
+import static com.android.storage.s2.S2Support.cellIdToString;
+
+import com.android.storage.block.read.BlockData;
+import com.android.storage.block.write.BlockWriter;
+import com.android.storage.block.write.EmptyBlockWriter;
+import com.android.storage.io.write.TypedOutputStream;
+import com.android.storage.s2.S2LevelRange;
+import com.android.storage.s2.S2Support;
+import com.android.storage.table.packed.write.PackedTableWriter;
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+import com.android.telephony.sats2range.read.SuffixTableExtraInfo;
+import com.android.telephony.sats2range.read.SuffixTableSharedData;
+
+import java.io.ByteArrayOutputStream;
+import java.io.File;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.nio.MappedByteBuffer;
+import java.nio.channels.FileChannel;
+import java.nio.file.StandardOpenOption;
+
+/**
+ * A class used to generate suffix tables block info and block data.
+ * To write empty tables use {@link #createEmptyBlockWriter()}.
+ * To write populated tables use {@link
+ * #createPopulated(SatS2RangeFileFormat, SuffixTableSharedData)} and add entries with
+ * {@link #addRange(S2LevelRange)}
+ */
+public final class SuffixTableWriter implements BlockWriter {
+
+ private final SuffixTableSharedData mSharedData;
+
+ private final SatS2RangeFileFormat mFileFormat;
+
+ private final PackedTableWriter mPackedTableWriter;
+
+ private final File mFile;
+
+ private S2LevelRange mLastRangeAdded;
+
+ private SuffixTableWriter(SatS2RangeFileFormat fileFormat, SuffixTableSharedData sharedData)
+ throws IOException {
+ mFileFormat = fileFormat;
+ mSharedData = sharedData;
+
+ int keySizeBits = fileFormat.getSuffixBitCount();
+ int entrySizeByteCount = fileFormat.getTableEntryByteCount();
+ mFile = File.createTempFile("suffixtablewriter", ".packed");
+
+ byte[] blockSharedData = SuffixTableSharedDataWriter.toBytes(sharedData);
+ FileOutputStream fileOutputStream = new FileOutputStream(mFile);
+ boolean signedValue = false;
+ mPackedTableWriter = PackedTableWriter.create(
+ fileOutputStream, entrySizeByteCount, keySizeBits, signedValue, blockSharedData);
+ }
+
+ /** Returns a {@link BlockWriter} capable of generating the block data for an empty table. */
+ public static BlockWriter createEmptyBlockWriter() {
+ return new EmptyBlockWriter(SatS2RangeFileFormat.BLOCK_TYPE_SUFFIX_TABLE);
+ }
+
+ /** Returns a {@link BlockWriter} capable of generating the block data for a populated table. */
+ public static SuffixTableWriter createPopulated(
+ SatS2RangeFileFormat fileFormat, SuffixTableSharedData sharedData) throws IOException {
+ return new SuffixTableWriter(fileFormat, sharedData);
+ }
+
+ /**
+ * Adds the supplied range to the table. The range must start after any previously added range,
+ * no overlap is allowed. Gaps are permitted. The range must have the expected S2 cell ID
+ * prefix. Invalid ranges will cause {@link IllegalArgumentException}. This method must be
+ * called at least once. See {@link SuffixTableWriter#createEmptyBlockWriter()} for empty
+ * tables.
+ */
+ public void addRange(S2LevelRange suffixTableRange) throws IOException {
+ checkIsOpen();
+
+ long rangeStartCellId = suffixTableRange.getStartCellId();
+ long rangeEndCellId = suffixTableRange.getEndCellId();
+
+ // Check range belongs in this table.
+ int rangeStartPrefixValue = mFileFormat.extractPrefixValueFromCellId(rangeStartCellId);
+ int rangeStartSuffixValue = mFileFormat.extractSuffixValueFromCellId(rangeStartCellId);
+ if (rangeStartPrefixValue != mSharedData.getTablePrefix()) {
+ throw new IllegalArgumentException(
+ "rangeStartCellId=" + cellIdToString(rangeStartCellId)
+ + " has a different prefix=" + rangeStartPrefixValue
+ + " than the table prefix=" + mSharedData.getTablePrefix());
+ }
+
+ long rangeEndCellIdInclusive = S2Support.offsetCellId(rangeEndCellId, -1);
+ int rangeEndPrefixValue = mFileFormat.extractPrefixValueFromCellId(rangeEndCellIdInclusive);
+ if (rangeEndPrefixValue != rangeStartPrefixValue) {
+ // Because SuffixTableRange has an exclusive end value, rangeEndPrefixValue is allowed
+ // to be the next prefix value if the rangeEndSuffixValue == 0.
+ int rangeEndSuffixValue = mFileFormat.extractSuffixValueFromCellId(rangeEndCellId);
+ if (!(rangeEndPrefixValue == rangeStartPrefixValue + 1 && rangeEndSuffixValue == 0)) {
+ throw new IllegalArgumentException("rangeEndPrefixValue=" + rangeEndPrefixValue
+ + " != rangeStartPrefixValue=" + rangeStartPrefixValue);
+ }
+ }
+
+ // Confirm the new range starts after the end of the last one that was added, if any.
+ if (mLastRangeAdded != null) {
+ long lastRangeAddedEndCellId = mLastRangeAdded.getEndCellId();
+ int lastRangeEndPrefixValue =
+ mFileFormat.extractPrefixValueFromCellId(lastRangeAddedEndCellId);
+ if (lastRangeEndPrefixValue != mSharedData.getTablePrefix()) {
+ // Deal with the special case where the last range added completed the table.
+ throw new IllegalArgumentException(
+ "Suffix table is full: last range added=" + mLastRangeAdded);
+ } else {
+ int lastRangeEndSuffixValue =
+ mFileFormat.extractSuffixValueFromCellId(lastRangeAddedEndCellId);
+ if (rangeStartSuffixValue < lastRangeEndSuffixValue) {
+ throw new IllegalArgumentException("suffixTableRange=" + suffixTableRange
+ + " overlaps with last range added=" + mLastRangeAdded);
+ }
+ }
+ }
+
+ int rangeLength = mFileFormat.calculateRangeLength(rangeStartCellId, rangeEndCellId);
+
+ long value = mFileFormat.createSuffixTableValue(rangeLength);
+ mPackedTableWriter.addEntry(rangeStartSuffixValue, value);
+ mLastRangeAdded = suffixTableRange;
+ }
+
+ @Override
+ public ReadBack close() throws IOException {
+ checkIsOpen();
+ mPackedTableWriter.close();
+ mLastRangeAdded = null;
+
+ int entryCount = mPackedTableWriter.getEntryCount();
+ if (entryCount == 0) {
+ throw new IllegalStateException("No ranges added. For an empty suffix table, use"
+ + " createEmptySuffixTableBlockWriter()");
+ }
+
+ FileChannel fileChannel = FileChannel.open(mFile.toPath(), StandardOpenOption.READ);
+ MappedByteBuffer map = fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, mFile.length());
+ fileChannel.close();
+
+ // Writes the number of entries into the extra bytes stored in the BlockInfo. This means the
+ // number of entries can be known without reading the block data at all.
+ SuffixTableExtraInfo suffixTableExtraInfo =
+ new SuffixTableExtraInfo(mSharedData.getTablePrefix(), entryCount);
+ byte[] blockInfoExtraBytes = generateBlockInfoExtraBytes(suffixTableExtraInfo);
+ BlockData blockData = new BlockData(map);
+ return new ReadBack() {
+ @Override
+ public byte[] getExtraBytes() {
+ return blockInfoExtraBytes;
+ }
+
+ @Override
+ public int getType() {
+ return SatS2RangeFileFormat.BLOCK_TYPE_SUFFIX_TABLE;
+ }
+
+ @Override
+ public BlockData getBlockData() {
+ return blockData;
+ }
+ };
+ }
+
+ private void checkIsOpen() {
+ if (!mPackedTableWriter.isOpen()) {
+ throw new IllegalStateException("Writer is closed.");
+ }
+ }
+
+ private static byte[] generateBlockInfoExtraBytes(SuffixTableExtraInfo suffixTableBlockInfo) {
+ ByteArrayOutputStream baos = new ByteArrayOutputStream();
+ try (TypedOutputStream tos = new TypedOutputStream(baos)) {
+ tos.writeInt(suffixTableBlockInfo.getEntryCount());
+ } catch (IOException e) {
+ throw new IllegalStateException("Unexpected IOException writing to byte array", e);
+ }
+ return baos.toByteArray();
+ }
+}
diff --git a/utils/satellite/tools/Android.bp b/utils/satellite/tools/Android.bp
new file mode 100644
index 0000000..9aacdd9
--- /dev/null
+++ b/utils/satellite/tools/Android.bp
@@ -0,0 +1,71 @@
+// Copyright (C) 2020 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package {
+ default_applicable_licenses: ["Android-Apache-2.0"],
+}
+
+java_library_host {
+ name: "satellite-s2storage-tools",
+ srcs: [
+ "src/main/java/**/*.java",
+ ],
+ static_libs: [
+ "jcommander",
+ "guava",
+ "satellite-s2storage-rw",
+ "s2storage_tools",
+ "s2-geometry-library-java",
+ ],
+}
+
+// A tool to create a binary satellite S2 file.
+java_binary_host {
+ name: "satellite_createsats2file",
+ main_class: "com.android.telephony.tools.sats2.CreateSatS2File",
+ static_libs: [
+ "satellite-s2storage-tools",
+ ],
+}
+
+// A tool to create a test satellite S2 file.
+java_binary_host {
+ name: "satellite_createsats2file_test",
+ main_class: "com.android.telephony.tools.sats2.CreateTestSatS2File",
+ static_libs: [
+ "satellite-s2storage-tools",
+ ],
+}
+
+// A tool to dump a satellite S2 file as text for debugging.
+java_binary_host {
+ name: "satellite_dumpsats2file",
+ main_class: "com.android.telephony.tools.sats2.DumpSatS2File",
+ static_libs: [
+ "satellite-s2storage-tools",
+ ],
+}
+
+// Tests for CreateSatS2File.
+java_test_host {
+ name: "SatelliteToolsTests",
+ srcs: ["src/test/java/**/*.java"],
+ static_libs: [
+ "junit",
+ "satellite-s2storage-tools",
+ "s2-geometry-library-java",
+ "satellite-s2storage-testutils"
+ ],
+ test_suites: ["general-tests"],
+}
\ No newline at end of file
diff --git a/utils/satellite/tools/TEST_MAPPING b/utils/satellite/tools/TEST_MAPPING
new file mode 100644
index 0000000..df9511a
--- /dev/null
+++ b/utils/satellite/tools/TEST_MAPPING
@@ -0,0 +1,7 @@
+{
+ "postsubmit": [
+ {
+ "name": "SatelliteToolsTests"
+ }
+ ]
+}
\ No newline at end of file
diff --git a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/CreateSatS2File.java b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/CreateSatS2File.java
new file mode 100644
index 0000000..f82cd5c
--- /dev/null
+++ b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/CreateSatS2File.java
@@ -0,0 +1,72 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.tools.sats2;
+
+import com.beust.jcommander.JCommander;
+import com.beust.jcommander.Parameter;
+import com.beust.jcommander.ParameterException;
+
+/** Creates a Sat S2 file from the list of S2 cells. */
+public final class CreateSatS2File {
+ /**
+ * Usage:
+ * CreateSatS2File <[input] s2 cells file> <[input] s2 level of input data>
+ * <[input] whether s2 cells is an allowed list> <[output] sat s2 file>
+ */
+ public static void main(String[] args) throws Exception {
+ Arguments arguments = new Arguments();
+ JCommander.newBuilder()
+ .addObject(arguments)
+ .build()
+ .parse(args);
+ String inputFile = arguments.inputFile;
+ int s2Level = arguments.s2Level;
+ String outputFile = arguments.outputFile;
+ boolean isAllowedList = Arguments.getBooleanValue(arguments.isAllowedList);
+ SatS2FileCreator.create(inputFile, s2Level, isAllowedList, outputFile);
+ }
+
+ private static class Arguments {
+ @Parameter(names = "--input-file",
+ description = "s2 cells file",
+ required = true)
+ public String inputFile;
+
+ @Parameter(names = "--s2-level",
+ description = "s2 level of input data",
+ required = true)
+ public int s2Level;
+
+ @Parameter(names = "--is-allowed-list",
+ description = "whether s2 cells file contains an allowed list of cells",
+ required = true)
+ public String isAllowedList;
+
+ @Parameter(names = "--output-file",
+ description = "sat s2 file",
+ required = true)
+ public String outputFile;
+
+ public static Boolean getBooleanValue(String value) {
+ if ("false".equalsIgnoreCase(value) || "true".equalsIgnoreCase(value)) {
+ return Boolean.parseBoolean(value);
+ } else {
+ throw new ParameterException("Invalid boolean string:" + value);
+ }
+ }
+ }
+}
diff --git a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/CreateTestSatS2File.java b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/CreateTestSatS2File.java
new file mode 100644
index 0000000..f9a9347
--- /dev/null
+++ b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/CreateTestSatS2File.java
@@ -0,0 +1,65 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.tools.sats2;
+
+import com.android.storage.s2.S2LevelRange;
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+import com.android.telephony.sats2range.write.SatS2RangeFileWriter;
+
+import java.io.File;
+import java.util.Arrays;
+import java.util.List;
+
+/** Creates a Sat S2 file with a small amount of test data. Useful for testing other tools. */
+public final class CreateTestSatS2File {
+
+ /**
+ * Usage:
+ * CreateTestSatS2File <file name>
+ */
+ public static void main(String[] args) throws Exception {
+ File file = new File(args[0]);
+
+ SatS2RangeFileFormat fileFormat = FileFormats.getFileFormatForLevel(12, true);
+ if (fileFormat.getPrefixBitCount() != 11) {
+ throw new IllegalStateException("Fake data requires 11 prefix bits");
+ }
+
+ try (SatS2RangeFileWriter satS2RangeFileWriter =
+ SatS2RangeFileWriter.open(file, fileFormat)) {
+ // Two ranges that share a prefix.
+ S2LevelRange range1 = new S2LevelRange(
+ fileFormat.createCellId(0b100_11111111, 1000),
+ fileFormat.createCellId(0b100_11111111, 2000));
+ S2LevelRange range2 = new S2LevelRange(
+ fileFormat.createCellId(0b100_11111111, 2000),
+ fileFormat.createCellId(0b100_11111111, 3000));
+ // This range has a different face, so a different prefix, and will be in a different
+ // suffix table.
+ S2LevelRange range3 = new S2LevelRange(
+ fileFormat.createCellId(0b101_11111111, 1000),
+ fileFormat.createCellId(0b101_11111111, 2000));
+ List<S2LevelRange> allRanges = listOf(range1, range2, range3);
+ satS2RangeFileWriter.createSortedSuffixBlocks(allRanges.iterator());
+ }
+ }
+
+ @SafeVarargs
+ private static <E> List<E> listOf(E... values) {
+ return Arrays.asList(values);
+ }
+}
diff --git a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/DumpSatS2File.java b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/DumpSatS2File.java
new file mode 100644
index 0000000..2a9ce37
--- /dev/null
+++ b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/DumpSatS2File.java
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.tools.sats2;
+
+import com.android.storage.tools.block.DumpBlockFile;
+import com.android.telephony.sats2range.read.SatS2RangeFileReader;
+import com.android.telephony.tools.sats2.dump.SatS2RangeFileDumper;
+
+import java.io.File;
+
+/**
+ * Dumps information about a Sat S2 data file. Like {@link DumpBlockFile} but it knows details about
+ * the Sat S2 format and can provide more detailed information.
+ */
+public final class DumpSatS2File {
+
+ /**
+ * Usage:
+ * DumpSatFile <[input] sat s2 file name> <[output] output directory name>
+ */
+ public static void main(String[] args) throws Exception {
+ String satS2FileName = args[0];
+ String outputDirName = args[1];
+
+ File outputDir = new File(outputDirName);
+ outputDir.mkdirs();
+
+ File satS2File = new File(satS2FileName);
+ try (SatS2RangeFileReader reader = SatS2RangeFileReader.open(satS2File)) {
+ reader.visit(new SatS2RangeFileDumper(outputDir));
+ }
+ }
+}
diff --git a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/FileFormats.java b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/FileFormats.java
new file mode 100644
index 0000000..b800897
--- /dev/null
+++ b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/FileFormats.java
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.tools.sats2;
+
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+
+/** Some sample file formats. */
+public final class FileFormats {
+
+ // level 12: 27 S2 cell ID bits split 11 + 16,
+ // suffix table: 24 bits, 16/24 for cell id suffix, 8/24 dedicated to range
+ private static final SatS2RangeFileFormat FILE_FORMAT_12_ALLOWED_LIST =
+ new SatS2RangeFileFormat(12, 11, 16, 1, 24, true);
+ private static final SatS2RangeFileFormat FILE_FORMAT_12_DISALLOWED_LIST =
+ new SatS2RangeFileFormat(12, 11, 16, 1, 24, false);
+
+ // level 14: 31 S2 cell ID bits split 13 + 18,
+ // suffix table: 32 bits, 18/32 for cell id suffix, 14/32 dedicated to range
+ private static final SatS2RangeFileFormat FILE_FORMAT_14_ALLOWED_LIST =
+ new SatS2RangeFileFormat(14, 13, 18, 1, 32, true);
+ private static final SatS2RangeFileFormat FILE_FORMAT_14_DISALLOWED_LIST =
+ new SatS2RangeFileFormat(14, 13, 18, 1, 32, false);
+
+ // level 16: 35 S2 cell ID bits split 13 + 22,
+ // suffix table: 32 bits, 22/32 for cell id suffix, 10/32 dedicated to range
+ private static final SatS2RangeFileFormat FILE_FORMAT_16_ALLOWED_LIST =
+ new SatS2RangeFileFormat(16, 13, 22, 1, 32, true);
+ private static final SatS2RangeFileFormat FILE_FORMAT_16_DISALLOWED_LIST =
+ new SatS2RangeFileFormat(16, 13, 22, 1, 32, false);
+
+ /** Maps an S2 level to one of the file format constants declared on by class. */
+ public static SatS2RangeFileFormat getFileFormatForLevel(int s2Level, boolean isAllowedList) {
+ switch (s2Level) {
+ case 12:
+ return isAllowedList ? FILE_FORMAT_12_ALLOWED_LIST : FILE_FORMAT_12_DISALLOWED_LIST;
+ case 14:
+ return isAllowedList ? FILE_FORMAT_14_ALLOWED_LIST : FILE_FORMAT_14_DISALLOWED_LIST;
+ case 16:
+ return isAllowedList ? FILE_FORMAT_16_ALLOWED_LIST : FILE_FORMAT_16_DISALLOWED_LIST;
+ default:
+ throw new IllegalArgumentException("s2Level=" + s2Level
+ + ", isAllowedList=" + isAllowedList + " not mapped");
+ }
+ }
+}
diff --git a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/SatS2FileCreator.java b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/SatS2FileCreator.java
new file mode 100644
index 0000000..b701a7b
--- /dev/null
+++ b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/SatS2FileCreator.java
@@ -0,0 +1,246 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.tools.sats2;
+
+import com.android.storage.s2.S2LevelRange;
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+import com.android.telephony.sats2range.read.SatS2RangeFileReader;
+import com.android.telephony.sats2range.write.SatS2RangeFileWriter;
+
+import com.google.common.base.Stopwatch;
+import com.google.common.geometry.S2CellId;
+
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.InputStream;
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Objects;
+import java.util.Scanner;
+import java.util.concurrent.TimeUnit;
+import java.util.stream.Collectors;
+
+/** A util class for creating a satellite S2 file from the list of S2 cells. */
+public final class SatS2FileCreator {
+ /**
+ * @param inputFile The input text file containing the list of S2 Cell IDs. Each line in the
+ * file contains a number in the range of a signed-64bit number which
+ * represents the ID of a S2 cell.
+ * @param s2Level The S2 level of all S2 cells in the input file.
+ * @param isAllowedList {@code true} means the input file contains an allowed list of S2 cells.
+ * {@code false} means the input file contains a disallowed list of S2
+ * cells.
+ * @param outputFile The output file to which the satellite S2 data in block format will be
+ * written.
+ */
+ public static void create(String inputFile, int s2Level, boolean isAllowedList,
+ String outputFile) throws Exception {
+ // Read a list of S2 cells from input file
+ List<Long> s2Cells = readS2CellsFromFile(inputFile);
+ System.out.println("Number of S2 cells read from file:" + s2Cells.size());
+
+ // Convert the input list of S2 Cells into the list of sorted S2CellId
+ List<S2CellId> sortedS2CellIds = s2Cells.stream()
+ .map(x -> new S2CellId(x))
+ .collect(Collectors.toList());
+ // IDs of S2CellId are converted to unsigned long numbers, which will be then used to
+ // compare S2CellId.
+ Collections.sort(sortedS2CellIds);
+
+ // Compress the list of S2CellId into S2 ranges
+ List<SatS2Range> satS2Ranges = createSatS2Ranges(sortedS2CellIds, s2Level);
+
+ // Write the S2 ranges into a block file
+ SatS2RangeFileFormat fileFormat =
+ FileFormats.getFileFormatForLevel(s2Level, isAllowedList);
+ try (SatS2RangeFileWriter satS2RangeFileWriter =
+ SatS2RangeFileWriter.open(new File(outputFile), fileFormat)) {
+ Iterator<S2LevelRange> s2LevelRangeIterator = satS2Ranges
+ .stream()
+ .map(x -> new S2LevelRange(x.rangeStart.id(), x.rangeEnd.id()))
+ .iterator();
+ /*
+ * Group the sorted ranges into contiguous suffix blocks. Big ranges might get split as
+ * needed to fit them into suffix blocks.
+ */
+ satS2RangeFileWriter.createSortedSuffixBlocks(s2LevelRangeIterator);
+ }
+
+ // Validate the output block file
+ System.out.println("Validating the output block file...");
+ try (SatS2RangeFileReader satS2RangeFileReader =
+ SatS2RangeFileReader.open(new File(outputFile))) {
+ if (isAllowedList != satS2RangeFileReader.isAllowedList()) {
+ throw new IllegalStateException("isAllowedList="
+ + satS2RangeFileReader.isAllowedList() + " does not match the input "
+ + "argument=" + isAllowedList);
+ }
+
+ // Verify that all input S2 cells are present in the output block file
+ for (S2CellId s2CellId : sortedS2CellIds) {
+ if (satS2RangeFileReader.findEntryByCellId(s2CellId.id()) == null) {
+ throw new IllegalStateException("s2CellId=" + s2CellId
+ + " is not present in the output sat s2 file");
+ }
+ }
+
+ // Verify the cell right before the first cell in the sortedS2CellIds is not present in
+ // the output block file
+ S2CellId prevCell = sortedS2CellIds.get(0).prev();
+ if (!sortedS2CellIds.contains(prevCell)
+ && satS2RangeFileReader.findEntryByCellId(prevCell.id()) != null) {
+ throw new IllegalStateException("The cell " + prevCell + ", which is right "
+ + "before the first cell is unexpectedly present in the output sat s2"
+ + " file");
+ } else {
+ System.out.println("prevCell=" + prevCell + " is in the sortedS2CellIds");
+ }
+
+ // Verify the cell right after the last cell in the sortedS2CellIds is not present in
+ // the output block file
+ S2CellId nextCell = sortedS2CellIds.get(sortedS2CellIds.size() - 1).next();
+ if (!sortedS2CellIds.contains(nextCell)
+ && satS2RangeFileReader.findEntryByCellId(nextCell.id()) != null) {
+ throw new IllegalStateException("The cell " + nextCell + ", which is right "
+ + "after the last cell is unexpectedly present in the output sat s2"
+ + " file");
+ } else {
+ System.out.println("nextCell=" + nextCell + " is in the sortedS2CellIds");
+ }
+ }
+ System.out.println("Successfully validated the output block file");
+ }
+
+ /**
+ * Read a list of S2 cells from the inputFile.
+ *
+ * @param inputFile A file containing the list of S2 cells. Each line in the inputFile contains
+ * a long number - the ID of a S2 cell.
+ * @return A list of S2 cells.
+ */
+ private static List<Long> readS2CellsFromFile(String inputFile) throws Exception {
+ List<Long> s2Cells = new ArrayList();
+ InputStream inputStream = new FileInputStream(inputFile);
+ try (Scanner scanner = new Scanner(inputStream, StandardCharsets.UTF_8.name())) {
+ while (scanner.hasNextLong()) {
+ s2Cells.add(scanner.nextLong());
+ }
+ if (scanner.hasNextLine()) {
+ throw new IllegalStateException("Input s2 cell file has invalid format, "
+ + "current line=" + scanner.nextLine());
+ }
+ }
+ return s2Cells;
+ }
+
+ /**
+ * Compress the list of sorted S2CellId into S2 ranges.
+ *
+ * @param sortedS2CellIds List of S2CellId sorted in ascending order.
+ * @param s2Level The level of all S2CellId.
+ * @return List of S2 ranges.
+ */
+ private static List<SatS2Range> createSatS2Ranges(List<S2CellId> sortedS2CellIds, int s2Level) {
+ Stopwatch stopwatch = Stopwatch.createStarted();
+ List<SatS2Range> ranges = new ArrayList<>();
+ if (sortedS2CellIds != null && sortedS2CellIds.size() > 0) {
+ S2CellId rangeStart = null;
+ S2CellId rangeEnd = null;
+ for (int i = 0; i < sortedS2CellIds.size(); i++) {
+ S2CellId currentS2CellId = sortedS2CellIds.get(i);
+ checkCellIdIsAtLevel(currentS2CellId, s2Level);
+
+ SatS2Range currentRange = createS2Range(currentS2CellId, s2Level);
+ S2CellId currentS2CellRangeStart = currentRange.rangeStart;
+ S2CellId currentS2CellRangeEnd = currentRange.rangeEnd;
+
+ if (rangeStart == null) {
+ // First time round the loop initialize rangeStart / rangeEnd only.
+ rangeStart = currentS2CellRangeStart;
+ } else if (rangeEnd.id() != currentS2CellRangeStart.id()) {
+ // If there's a gap between cellIds, store the range we have so far and start a
+ // new range.
+ ranges.add(new SatS2Range(rangeStart, rangeEnd));
+ rangeStart = currentS2CellRangeStart;
+ }
+ rangeEnd = currentS2CellRangeEnd;
+ }
+ ranges.add(new SatS2Range(rangeStart, rangeEnd));
+ }
+
+ // Sorting the ranges is not necessary. As the input is sorted , it will already be sorted.
+ System.out.printf("Created %s SatS2Ranges in %s milliseconds\n",
+ ranges.size(), stopwatch.elapsed(TimeUnit.MILLISECONDS));
+ return ranges;
+ }
+
+ /**
+ * @return A pair of S2CellId for the range [s2CellId, s2CellId's next sibling)
+ */
+ private static SatS2Range createS2Range(
+ S2CellId s2CellId, int s2Level) {
+ // Since s2CellId is at s2Level, s2CellId.childBegin(s2Level) returns itself.
+ S2CellId firstS2CellRangeStart = s2CellId.childBegin(s2Level);
+ // Get the immediate next sibling of s2CellId
+ S2CellId firstS2CellRangeEnd = s2CellId.childEnd(s2Level);
+
+ if (firstS2CellRangeEnd.face() < firstS2CellRangeStart.face()
+ || !firstS2CellRangeEnd.isValid()) {
+ // Fix this if it becomes an issue.
+ throw new IllegalStateException("firstS2CellId=" + s2CellId
+ + ", childEnd(" + s2Level + ") produced an unsupported"
+ + " value=" + firstS2CellRangeEnd);
+ }
+ return new SatS2Range(firstS2CellRangeStart, firstS2CellRangeEnd);
+ }
+
+ private static void checkCellIdIsAtLevel(S2CellId cellId, int s2Level) {
+ if (cellId.level() != s2Level) {
+ throw new IllegalStateException("Bad level for cellId=" + cellId
+ + ". Must be s2Level=" + s2Level);
+ }
+ }
+
+ /**
+ * A range of S2 cell IDs at a fixed S2 level. The range is expressed as a start cell ID
+ * (inclusive) and an end cell ID (exclusive).
+ */
+ private static class SatS2Range {
+ public final S2CellId rangeStart;
+ public final S2CellId rangeEnd;
+
+ /**
+ * Creates an instance. If the range is invalid or the cell IDs are from different levels
+ * this method throws an {@link IllegalArgumentException}.
+ */
+ SatS2Range(S2CellId rangeStart, S2CellId rangeEnd) {
+ this.rangeStart = Objects.requireNonNull(rangeStart);
+ this.rangeEnd = Objects.requireNonNull(rangeEnd);
+ if (rangeStart.level() != rangeEnd.level()) {
+ throw new IllegalArgumentException(
+ "Levels differ: rangeStart=" + rangeStart + ", rangeEnd=" + rangeEnd);
+ }
+ if (rangeStart.greaterOrEquals(rangeEnd)) {
+ throw new IllegalArgumentException(
+ "Range start (" + rangeStart + " >= range end (" + rangeEnd + ")");
+ }
+ }
+ }
+}
diff --git a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/dump/HeaderBlockDumper.java b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/dump/HeaderBlockDumper.java
new file mode 100644
index 0000000..69a3f70
--- /dev/null
+++ b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/dump/HeaderBlockDumper.java
@@ -0,0 +1,40 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.tools.sats2.dump;
+
+import com.android.storage.tools.block.dump.SingleFileDumper;
+import com.android.telephony.sats2range.read.HeaderBlock;
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+
+import java.io.File;
+
+/** A {@link HeaderBlock.HeaderBlockVisitor} that dumps information to a file. */
+final class HeaderBlockDumper extends SingleFileDumper implements HeaderBlock.HeaderBlockVisitor {
+
+ HeaderBlockDumper(File headerBlockFile) {
+ super(headerBlockFile);
+ }
+
+ @Override
+ public void visitFileFormat(SatS2RangeFileFormat fileFormat) {
+ println("File format");
+ println("===========");
+ println(fileFormat.toString());
+ println();
+ }
+}
+
diff --git a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/dump/SatS2RangeFileDumper.java b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/dump/SatS2RangeFileDumper.java
new file mode 100644
index 0000000..307275a
--- /dev/null
+++ b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/dump/SatS2RangeFileDumper.java
@@ -0,0 +1,85 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.tools.sats2.dump;
+
+import static com.android.storage.tools.block.dump.DumpUtils.binaryStringLength;
+import static com.android.storage.tools.block.dump.DumpUtils.hexStringLength;
+import static com.android.storage.tools.block.dump.DumpUtils.zeroPadBinary;
+import static com.android.storage.tools.block.dump.DumpUtils.zeroPadHex;
+
+import com.android.storage.tools.block.dump.SingleFileDumper;
+import com.android.telephony.sats2range.read.HeaderBlock;
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+import com.android.telephony.sats2range.read.SatS2RangeFileReader;
+import com.android.telephony.sats2range.read.SuffixTableBlock;
+import com.android.telephony.sats2range.read.SuffixTableExtraInfo;
+
+import java.io.File;
+
+/** A {@link SatS2RangeFileReader.SatS2RangeFileVisitor} that dumps information to a file. */
+public final class SatS2RangeFileDumper implements SatS2RangeFileReader.SatS2RangeFileVisitor {
+
+ private final File mOutputDir;
+
+ private int mMaxPrefix;
+
+ private int mMaxPrefixBinaryLength;
+
+ private int mMaxPrefixHexLength;
+
+ private SingleFileDumper mExtraInfoDumper;
+
+ public SatS2RangeFileDumper(File outputDir) {
+ mOutputDir = outputDir;
+ }
+
+ @Override
+ public void begin() throws VisitException {
+ mExtraInfoDumper = new SingleFileDumper(new File(mOutputDir, "suffixtable_extrainfo.txt"));
+ mExtraInfoDumper.begin();
+ }
+
+ @Override
+ public void visitSuffixTableExtraInfo(SuffixTableExtraInfo suffixTableExtraInfo) {
+ int prefix = suffixTableExtraInfo.getPrefix();
+ mExtraInfoDumper.println("prefix=" + zeroPadBinary(mMaxPrefixBinaryLength, prefix)
+ + "(" + zeroPadHex(mMaxPrefixHexLength, prefix) + ")"
+ + ", entryCount=" + suffixTableExtraInfo.getEntryCount());
+ }
+
+ @Override
+ public void visitHeaderBlock(HeaderBlock headerBlock) throws VisitException {
+ File headerFile = new File(mOutputDir, "header.txt");
+ headerBlock.visit(new HeaderBlockDumper(headerFile));
+ SatS2RangeFileFormat fileFormat = headerBlock.getFileFormat();
+ mMaxPrefix = fileFormat.getMaxPrefixValue();
+ mMaxPrefixBinaryLength = binaryStringLength(mMaxPrefix);
+ mMaxPrefixHexLength = hexStringLength(mMaxPrefix);
+ }
+
+ @Override
+ public void visitSuffixTableBlock(SuffixTableBlock suffixTableBlock)
+ throws VisitException {
+ suffixTableBlock.visit(new SuffixTableBlockDumper(mOutputDir, mMaxPrefix));
+ }
+
+ @Override
+ public void end() throws VisitException {
+ mExtraInfoDumper.end();
+ }
+}
+
diff --git a/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/dump/SuffixTableBlockDumper.java b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/dump/SuffixTableBlockDumper.java
new file mode 100644
index 0000000..a5d75b4
--- /dev/null
+++ b/utils/satellite/tools/src/main/java/com/android/telephony/tools/sats2/dump/SuffixTableBlockDumper.java
@@ -0,0 +1,66 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.tools.sats2.dump;
+
+import static com.android.storage.tools.block.dump.DumpUtils.binaryStringLength;
+import static com.android.storage.tools.block.dump.DumpUtils.createPrintWriter;
+import static com.android.storage.tools.block.dump.DumpUtils.generateDumpFile;
+import static com.android.storage.tools.block.dump.DumpUtils.hexStringLength;
+import static com.android.storage.tools.block.dump.DumpUtils.zeroPadBinary;
+import static com.android.storage.tools.block.dump.DumpUtils.zeroPadHex;
+
+import com.android.telephony.sats2range.read.SuffixTableBlock;
+
+import java.io.File;
+import java.io.PrintWriter;
+import java.util.Objects;
+
+/** A {@link SuffixTableBlock.SuffixTableBlockVisitor} that dumps information to a file. */
+public final class SuffixTableBlockDumper implements SuffixTableBlock.SuffixTableBlockVisitor {
+
+ private final File mOutputDir;
+
+ private final int mMaxPrefix;
+
+ public SuffixTableBlockDumper(File outputDir, int maxPrefix) {
+ mOutputDir = Objects.requireNonNull(outputDir);
+ mMaxPrefix = maxPrefix;
+ }
+
+ @Override
+ public void visit(SuffixTableBlock suffixTableBlock) throws VisitException {
+ int tablePrefix = suffixTableBlock.getPrefix();
+ int prefixHexLength = hexStringLength(tablePrefix);
+ int prefixBinaryLength = binaryStringLength(tablePrefix);
+ File suffixTableFile =
+ generateDumpFile(mOutputDir, "suffixtable_", tablePrefix, mMaxPrefix);
+ try (PrintWriter writer = createPrintWriter(suffixTableFile)) {
+ writer.println("Prefix value=" + zeroPadBinary(prefixBinaryLength, tablePrefix)
+ + " (" + zeroPadHex(prefixHexLength, tablePrefix) + ")");
+ int entryCount = suffixTableBlock.getEntryCount();
+ writer.println("Entry count=" + entryCount);
+ if (entryCount > 0) {
+ for (int i = 0; i < entryCount; i++) {
+ writer.println(
+ "[" + i + "]=" + suffixTableBlock.getEntryByIndex(i)
+ .getSuffixTableRange());
+ }
+ }
+ }
+ }
+}
+
diff --git a/utils/satellite/tools/src/test/java/com/android/telephony/tools/sats2/CreateSatS2FileTest.java b/utils/satellite/tools/src/test/java/com/android/telephony/tools/sats2/CreateSatS2FileTest.java
new file mode 100644
index 0000000..80c1807
--- /dev/null
+++ b/utils/satellite/tools/src/test/java/com/android/telephony/tools/sats2/CreateSatS2FileTest.java
@@ -0,0 +1,166 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.telephony.tools.sats2;
+
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.fail;
+
+import com.android.telephony.sats2range.read.SatS2RangeFileFormat;
+import com.android.telephony.sats2range.read.SatS2RangeFileReader;
+import com.android.telephony.sats2range.utils.TestUtils;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+
+
+/** Tests for {@link CreateSatS2File} */
+public final class CreateSatS2FileTest {
+ private Path mTempDirPath;
+
+ @Before
+ public void setUp() throws IOException {
+ mTempDirPath = TestUtils.createTempDir(this.getClass());
+ }
+
+ @After
+ public void tearDown() throws IOException {
+ if (mTempDirPath != null) {
+ TestUtils.deleteDirectory(mTempDirPath);
+ }
+ }
+
+ @Test
+ public void testCreateSatS2FileWithValidInput_AllowedList() throws Exception {
+ testCreateSatS2FileWithValidInput(true);
+ }
+
+ @Test
+ public void testCreateSatS2FileWithValidInput_DisallowedList() throws Exception {
+ testCreateSatS2FileWithValidInput(false);
+ }
+
+ @Test
+ public void testCreateSatS2FileWithInvalidInput() throws Exception {
+ int s2Level = 12;
+ boolean isAllowedList = true;
+ Path inputDirPath = mTempDirPath.resolve("input");
+ Files.createDirectory(inputDirPath);
+ Path inputFilePath = inputDirPath.resolve("s2cells.txt");
+
+ Path outputDirPath = mTempDirPath.resolve("output");
+ Files.createDirectory(outputDirPath);
+ Path outputFilePath = outputDirPath.resolve("sats2.dat");
+
+ // Create test input S2 cell file
+ SatS2RangeFileFormat fileFormat = FileFormats.getFileFormatForLevel(s2Level, isAllowedList);
+ TestUtils.createInvalidTestS2CellFile(inputFilePath.toFile(), fileFormat);
+
+ // Commandline input arguments
+ String[] args = {
+ "--input-file", inputFilePath.toAbsolutePath().toString(),
+ "--s2-level", String.valueOf(s2Level),
+ "--is-allowed-list", isAllowedList ? "true" : "false",
+ "--output-file", outputFilePath.toAbsolutePath().toString()
+ };
+
+ // Execute the tool CreateSatS2File and expect exception
+ try {
+ CreateSatS2File.main(args);
+ } catch (Exception ex) {
+ // Expected exception
+ return;
+ }
+ fail("Exception should have been caught");
+ }
+
+ private void testCreateSatS2FileWithValidInput(boolean isAllowedList) throws Exception {
+ int s2Level = 12;
+ Path inputDirPath = mTempDirPath.resolve("input");
+ Files.createDirectory(inputDirPath);
+ Path inputFilePath = inputDirPath.resolve("s2cells.txt");
+
+ Path outputDirPath = mTempDirPath.resolve("output");
+ Files.createDirectory(outputDirPath);
+ Path outputFilePath = outputDirPath.resolve("sats2.dat");
+
+ /*
+ * Create test input S2 cell file with the following ranges:
+ * 1) [(prefix=0b100_11111111, suffix=1000), (prefix=0b100_11111111, suffix=2000))
+ * 2) [(prefix=0b100_11111111, suffix=2001), (prefix=0b100_11111111, suffix=3000))
+ * 3) [(prefix=0b101_11111111, suffix=1000), (prefix=0b101_11111111, suffix=2001))
+ */
+ SatS2RangeFileFormat fileFormat = FileFormats.getFileFormatForLevel(s2Level, isAllowedList);
+ TestUtils.createValidTestS2CellFile(inputFilePath.toFile(), fileFormat);
+
+ // Commandline input arguments
+ String[] args = {
+ "--input-file", inputFilePath.toAbsolutePath().toString(),
+ "--s2-level", String.valueOf(s2Level),
+ "--is-allowed-list", isAllowedList ? "true" : "false",
+ "--output-file", outputFilePath.toAbsolutePath().toString()
+ };
+
+ // Execute the tool CreateSatS2File and expect successful result
+ try {
+ CreateSatS2File.main(args);
+ } catch (Exception ex) {
+ fail("Unexpected exception when executing the tool ex=" + ex);
+ }
+
+ // Validate the output block file
+ try {
+ SatS2RangeFileReader satS2RangeFileReader =
+ SatS2RangeFileReader.open(outputFilePath.toFile());
+ if (isAllowedList != satS2RangeFileReader.isAllowedList()) {
+ fail("isAllowedList="
+ + satS2RangeFileReader.isAllowedList() + " does not match the input "
+ + "argument=" + isAllowedList);
+ }
+
+ // Verify an edge cell (prefix=0b100_11111111, suffix=100)
+ long s2CellId = fileFormat.createCellId(0b100_11111111, 100);
+ assertNull(satS2RangeFileReader.findEntryByCellId(s2CellId));
+
+ // Verify a middle cell (prefix=0b100_11111111, suffix=2000)
+ s2CellId = fileFormat.createCellId(0b100_11111111, 2000);
+ assertNull(satS2RangeFileReader.findEntryByCellId(s2CellId));
+
+ // Verify an edge cell (prefix=0b100_11111111, suffix=4000)
+ s2CellId = fileFormat.createCellId(0b100_11111111, 4000);
+ assertNull(satS2RangeFileReader.findEntryByCellId(s2CellId));
+
+ // Verify an edge cell (prefix=0b101_11111111, suffix=500)
+ s2CellId = fileFormat.createCellId(0b101_11111111, 500);
+ assertNull(satS2RangeFileReader.findEntryByCellId(s2CellId));
+
+ // Verify an edge cell (prefix=0b101_11111111, suffix=2001)
+ s2CellId = fileFormat.createCellId(0b101_11111111, 2500);
+ assertNull(satS2RangeFileReader.findEntryByCellId(s2CellId));
+
+ // Verify an edge cell (prefix=0b101_11111111, suffix=2500)
+ s2CellId = fileFormat.createCellId(0b101_11111111, 2500);
+ assertNull(satS2RangeFileReader.findEntryByCellId(s2CellId));
+ } catch (Exception ex) {
+ fail("Unexpected exception when validating the output ex=" + ex);
+ }
+ }
+}