1 /* 2 * Copyright (C) 2023 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.telephony.sats2range.write; 18 19 import com.android.storage.block.write.BlockFileWriter; 20 import com.android.storage.block.write.BlockWriter; 21 import com.android.storage.block.write.EmptyBlockWriter; 22 import com.android.storage.s2.S2LevelRange; 23 import com.android.storage.s2.S2Support; 24 import com.android.telephony.sats2range.read.SatS2RangeFileFormat; 25 import com.android.telephony.sats2range.read.SuffixTableSharedData; 26 27 import java.io.File; 28 import java.io.IOException; 29 import java.util.ArrayDeque; 30 import java.util.ArrayList; 31 import java.util.Deque; 32 import java.util.Iterator; 33 import java.util.List; 34 35 /** Writes a satellite S2 data file. */ 36 public final class SatS2RangeFileWriter implements AutoCloseable { 37 38 private final HeaderBlockWriter mHeaderBlockWriter; 39 40 private final List<BlockWriter> mSuffixTableBlockWriters = new ArrayList<>(); 41 42 private final BlockFileWriter mBlockFileWriter; 43 44 private final SatS2RangeFileFormat mFileFormat; 45 SatS2RangeFileWriter(SatS2RangeFileFormat fileFormat, BlockFileWriter blockFileWriter)46 private SatS2RangeFileWriter(SatS2RangeFileFormat fileFormat, BlockFileWriter blockFileWriter) 47 throws IOException { 48 mBlockFileWriter = blockFileWriter; 49 mFileFormat = fileFormat; 50 51 mHeaderBlockWriter = HeaderBlockWriter.create(fileFormat); 52 } 53 54 /** Opens a file for writing with the specified format. */ open(File outFile, SatS2RangeFileFormat fileFormat)55 public static SatS2RangeFileWriter open(File outFile, SatS2RangeFileFormat fileFormat) 56 throws IOException { 57 BlockFileWriter writer = BlockFileWriter.open( 58 SatS2RangeFileFormat.MAGIC, SatS2RangeFileFormat.VERSION, outFile); 59 return new SatS2RangeFileWriter(fileFormat, writer); 60 } 61 62 /** 63 * Group the sorted ranges into contiguous suffix blocks. Big ranges might get split as 64 * needed to fit them into suffix blocks. The ranges must be of the expected S2 level 65 * and ordered by cell ID. 66 */ createSortedSuffixBlocks(Iterator<S2LevelRange> ranges)67 public void createSortedSuffixBlocks(Iterator<S2LevelRange> ranges) throws IOException { 68 PushBackIterator<S2LevelRange> pushBackIterator = new PushBackIterator<>(ranges); 69 70 // For each prefix value, collect all the ranges that match. 71 for (int currentPrefix = 0; 72 currentPrefix <= mFileFormat.getMaxPrefixValue(); 73 currentPrefix++) { 74 75 // Step 1: 76 // populate samePrefixRanges, which holds ranges that have a prefix of currentPrefix. 77 List<S2LevelRange> samePrefixRanges = 78 collectSamePrefixRanges(pushBackIterator, currentPrefix); 79 80 // Step 2: Write samePrefixRanges to a suffix table. 81 BlockWriter blockWriter = writeSamePrefixRanges(currentPrefix, samePrefixRanges); 82 mSuffixTableBlockWriters.add(blockWriter); 83 } 84 85 // At this point there should be no data left. 86 if (pushBackIterator.hasNext()) { 87 throw new IllegalStateException("Unexpected ranges left at the end."); 88 } 89 } 90 collectSamePrefixRanges( PushBackIterator<S2LevelRange> pushBackIterator, int currentPrefix)91 private List<S2LevelRange> collectSamePrefixRanges( 92 PushBackIterator<S2LevelRange> pushBackIterator, int currentPrefix) { 93 List<S2LevelRange> samePrefixRanges = new ArrayList<>(); 94 while (pushBackIterator.hasNext()) { 95 S2LevelRange currentRange = pushBackIterator.next(); 96 97 long startCellId = currentRange.getStartCellId(); 98 if (mFileFormat.getS2Level() != S2Support.getS2Level(startCellId)) { 99 throw new IllegalArgumentException( 100 "Input data level does not match file format level"); 101 } 102 int startCellPrefix = mFileFormat.extractPrefixValueFromCellId(startCellId); 103 if (startCellPrefix != currentPrefix) { 104 if (startCellPrefix < currentPrefix) { 105 throw new IllegalStateException("Prefix out of order:" 106 + " currentPrefixValue=" + currentPrefix 107 + " startCellPrefixValue=" + startCellPrefix); 108 } 109 // The next range is for a later prefix. Put it back and move to step 2. 110 pushBackIterator.pushBack(currentRange); 111 break; 112 } 113 114 long endCellId = currentRange.getEndCellId(); 115 if (mFileFormat.getS2Level() != S2Support.getS2Level(endCellId)) { 116 throw new IllegalArgumentException("endCellId in range " + currentRange 117 + " has the wrong S2 level"); 118 } 119 120 // Split ranges if they span a prefix. 121 int endCellPrefixValue = mFileFormat.extractPrefixValueFromCellId(endCellId); 122 if (startCellPrefix != endCellPrefixValue) { 123 // Create a range for the current prefix. 124 { 125 long newEndCellId = mFileFormat.createCellId(startCellPrefix + 1, 0); 126 S2LevelRange satS2Range = new S2LevelRange(startCellId, newEndCellId); 127 samePrefixRanges.add(satS2Range); 128 } 129 130 Deque<S2LevelRange> otherRanges = new ArrayDeque<>(); 131 // Intermediate prefixes. 132 startCellPrefix = startCellPrefix + 1; 133 while (startCellPrefix != endCellPrefixValue) { 134 long newStartCellId = mFileFormat.createCellId(startCellPrefix, 0); 135 long newEndCellId = mFileFormat.createCellId(startCellPrefix + 1, 0); 136 S2LevelRange satS2Range = new S2LevelRange(newStartCellId, newEndCellId); 137 otherRanges.add(satS2Range); 138 startCellPrefix++; 139 } 140 141 // Final prefix. 142 { 143 long newStartCellId = mFileFormat.createCellId(endCellPrefixValue, 0); 144 if (newStartCellId != endCellId) { 145 S2LevelRange satS2Range = new S2LevelRange(newStartCellId, endCellId); 146 otherRanges.add(satS2Range); 147 } 148 } 149 150 // Push back the ranges in reverse order so they come back out in sorted order. 151 while (!otherRanges.isEmpty()) { 152 pushBackIterator.pushBack(otherRanges.removeLast()); 153 } 154 break; 155 } else { 156 samePrefixRanges.add(currentRange); 157 } 158 } 159 return samePrefixRanges; 160 } 161 writeSamePrefixRanges( int currentPrefix, List<S2LevelRange> samePrefixRanges)162 private BlockWriter writeSamePrefixRanges( 163 int currentPrefix, List<S2LevelRange> samePrefixRanges) throws IOException { 164 BlockWriter blockWriter; 165 if (samePrefixRanges.size() == 0) { 166 // Add an empty block. 167 blockWriter = SuffixTableWriter.createEmptyBlockWriter(); 168 } else { 169 // Create a suffix table block. 170 SuffixTableSharedData sharedData = new SuffixTableSharedData(currentPrefix); 171 SuffixTableWriter suffixTableWriter = 172 SuffixTableWriter.createPopulated(mFileFormat, sharedData); 173 S2LevelRange lastRange = null; 174 for (S2LevelRange currentRange : samePrefixRanges) { 175 // Validate ranges don't overlap. 176 if (lastRange != null) { 177 if (lastRange.overlaps(currentRange)) { 178 throw new IllegalStateException("lastRange=" + lastRange + " overlaps" 179 + " currentRange=" + currentRange); 180 } 181 } 182 lastRange = currentRange; 183 184 // Split the range so it fits. 185 final int maxRangeLength = mFileFormat.getTableEntryMaxRangeLengthValue(); 186 long startCellId = currentRange.getStartCellId(); 187 long endCellId = currentRange.getEndCellId(); 188 int rangeLength = mFileFormat.calculateRangeLength(startCellId, endCellId); 189 while (rangeLength > maxRangeLength) { 190 long newEndCellId = S2Support.offsetCellId(startCellId, maxRangeLength); 191 S2LevelRange suffixTableRange = new S2LevelRange(startCellId, newEndCellId); 192 suffixTableWriter.addRange(suffixTableRange); 193 startCellId = newEndCellId; 194 rangeLength = mFileFormat.calculateRangeLength(startCellId, endCellId); 195 } 196 S2LevelRange suffixTableRange = new S2LevelRange(startCellId, endCellId); 197 suffixTableWriter.addRange(suffixTableRange); 198 } 199 blockWriter = suffixTableWriter; 200 } 201 return blockWriter; 202 } 203 204 @Override close()205 public void close() throws IOException { 206 try { 207 BlockWriter.ReadBack headerReadBack = mHeaderBlockWriter.close(); 208 mBlockFileWriter.addBlock(headerReadBack.getType(), headerReadBack.getExtraBytes(), 209 headerReadBack.getBlockData()); 210 211 // Add empty blocks padding. 212 EmptyBlockWriter emptyBlockWriterHelper = 213 new EmptyBlockWriter(SatS2RangeFileFormat.BLOCK_TYPE_PADDING); 214 BlockWriter.ReadBack emptyBlockReadBack = emptyBlockWriterHelper.close(); 215 for (int i = 0; i < mFileFormat.getSuffixTableBlockIdOffset() - 1; i++) { 216 mBlockFileWriter.addBlock( 217 emptyBlockReadBack.getType(), emptyBlockReadBack.getExtraBytes(), 218 emptyBlockReadBack.getBlockData()); 219 } 220 221 // Add the suffix tables. 222 for (BlockWriter blockWriter : mSuffixTableBlockWriters) { 223 BlockWriter.ReadBack readBack = blockWriter.close(); 224 225 mBlockFileWriter.addBlock(readBack.getType(), readBack.getExtraBytes(), 226 readBack.getBlockData()); 227 } 228 } finally { 229 mBlockFileWriter.close(); 230 } 231 } 232 233 /** Returns the{@link SatS2RangeFileFormat} for the file being written. */ getFileFormat()234 public SatS2RangeFileFormat getFileFormat() { 235 return mFileFormat; 236 } 237 } 238