1 /* 2 * Copyright (C) 2020 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.timezone.location.storage.s2; 18 19 import com.android.timezone.location.storage.util.BitwiseUtils; 20 21 /** A class that can perform basic S2 operations on cell IDs. */ 22 public final class S2Support { 23 24 /** The number of bits in an S2 long cell ID devoted to the face. */ 25 public static final int FACE_BIT_COUNT = 3; 26 27 /** The max S2 face ID. */ 28 public static final int MAX_FACE_ID = 5; 29 30 /** The maximum S2 level. */ 31 public static final int MAX_S2_LEVEL = 30; 32 33 private static final long FACE_BIT_MASK = 0b11100000L << 56; 34 35 private static final int BIT_COUNT_PER_LEVEL = 2; 36 37 /** The minimum cell ID. The index is S2 level. */ 38 private static final long[] MIN_CELL_ID; 39 40 /** The maximum cell ID The index is S2 level. */ 41 private static final long[] MAX_CELL_ID; 42 43 static { 44 MIN_CELL_ID = new long[MAX_S2_LEVEL + 1]; 45 MAX_CELL_ID = new long[MAX_S2_LEVEL + 1]; 46 for (int i = 0; i < MIN_CELL_ID.length; i++) { 47 MIN_CELL_ID[i] = calcMinS2CellId(i); 48 MAX_CELL_ID[i] = calcMaxS2CellId(i); 49 } 50 } 51 S2Support()52 private S2Support() { 53 } 54 55 /** Converts an S2 cell ID to a human readable form, e.g. for debugging. */ cellIdToString(long cellId)56 public static String cellIdToString(long cellId) { 57 int level = getS2Level(cellId); 58 int faceId = getValidFaceId(cellId); 59 long index = getValidIndex(cellId); 60 return Long.toUnsignedString(cellId) + " (level=" + level + " faceId=" + faceId 61 + " index=" + index + ")"; 62 } 63 getValidFaceId(long cellId)64 private static int getValidFaceId(long cellId) { 65 int faceId = getFaceIdValue(cellId); 66 checkValidFaceId(faceId); 67 return faceId; 68 } 69 70 /** Extracts the face ID bits from the cellId. Does not guarantee they are valid. */ getFaceIdValue(long cellId)71 private static int getFaceIdValue(long cellId) { 72 return (int) ((BitwiseUtils.getHighBitsMask(FACE_BIT_COUNT) & cellId) 73 >>> (Long.SIZE - FACE_BIT_COUNT)); 74 } 75 76 /** 77 * Extracts the cell index from the cellId. Throws IllegalArgumentException if the cell ID is 78 * invalid. 79 */ getValidIndex(long cellId)80 private static long getValidIndex(long cellId) { 81 // Unused bits is the final 1 followed by a variable number of zeros. 82 int unusedBitCount = Long.numberOfTrailingZeros(cellId) + 1; 83 if (unusedBitCount > Long.SIZE - FACE_BIT_COUNT) { 84 throw new IllegalArgumentException( 85 "There must be at least one bit set in every S2 cell ID"); 86 } else if (unusedBitCount % BIT_COUNT_PER_LEVEL == 0) { 87 throw new IllegalArgumentException("Invalid number of index bits in " + cellId); 88 } 89 long indexBits = cellId & ~FACE_BIT_MASK; 90 return indexBits >>> unusedBitCount; 91 } 92 93 /** 94 * Creates a cell ID of the specified level, face ID and index. e.g. index 0 is the first cell 95 * ID with that level and face ID, index 1 is the second, and so on. 96 * 97 * <p>If index is greater than or equal to the number of cells at the specified level an 98 * {@link IllegalArgumentException} is thrown. If level == 0, index must be zero, otherwise an 99 * {@link IllegalArgumentException} is thrown. 100 */ cellId(int level, int faceId, long index)101 public static long cellId(int level, int faceId, long index) { 102 checkValidFaceId(faceId); 103 104 if (index < 0) { 105 throw new IllegalArgumentException("index must be >= 0, index=" + index); 106 } 107 long maxIndexValue = getMaxIndex(level); 108 if (index > maxIndexValue) { 109 throw new IllegalArgumentException( 110 "index=" + index + " > the max index value at level=" + level 111 + " (" + maxIndexValue + ")"); 112 } 113 114 // storageBitCountForLevel includes the faceId and index bits, but not the trailing 1 needed 115 // to indicate level. 116 int storageBitCountForLevel = storageBitCountForLevel(level); 117 // indexBitCount is just the bits needed to store the index at the given level. 118 int indexBitCount = storageBitCountForLevel - FACE_BIT_COUNT; 119 120 // suffixBitCount excludes the face bits but includes trailing 1 needed to indicate level. 121 int suffixBitCount = indexBitCount + 1; 122 123 // Introduce the trailing 1 to the index to generate the suffix. 124 long suffix = (index << 1) | 1L; 125 126 long cellId = ((long) faceId) << suffixBitCount; 127 cellId |= suffix; 128 cellId <<= Long.SIZE - (storageBitCountForLevel + 1); 129 return cellId; 130 } 131 132 /** 133 * Returns the max index value permitted for the specified S2 level. For level 0, this method 134 * returns 0. 135 */ getMaxIndex(int s2Level)136 public static long getMaxIndex(int s2Level) { 137 checkValidLevel(s2Level); 138 return BitwiseUtils.getLowBitsMask(s2Level * BIT_COUNT_PER_LEVEL); 139 } 140 141 /** 142 * Returns the number of bits used to store cell IDs at the specified level. i.e. excluding the 143 * non-storage bits that consist of the trailing 1 used to indicate level and any zeros after 144 * it. 145 */ storageBitCountForLevel(int level)146 public static int storageBitCountForLevel(int level) { 147 checkValidLevel(level); 148 return FACE_BIT_COUNT + (BIT_COUNT_PER_LEVEL * level); 149 } 150 151 /** 152 * Throws an exception if the cell ID is invalid. 153 */ validateCellId(long cellId)154 public static void validateCellId(long cellId) { 155 getValidFaceId(cellId); 156 getValidIndex(cellId); 157 } 158 159 /** 160 * Offset the supplied cellId by {@code offset} cell IDs. offset can be negative. If the 161 * absolute value of {@code offset} is > the number of cell IDs at the S2 level of 162 * {@code cellId} then an {@link IllegalArgumentException} is thrown. 163 */ offsetCellId(long cellId, int offset)164 public static long offsetCellId(long cellId, int offset) { 165 // Validate the cell ID and capture values for use later. 166 int level = getS2Level(cellId); 167 int faceId = getValidFaceId(cellId); 168 169 // Special case offset 0 because it's trivial. 170 if (offset == 0) { 171 return cellId; 172 } 173 174 // Validate the offset and calculate index values. 175 final int faceCount = MAX_FACE_ID + 1; 176 177 long cellsPerFace = 0; 178 long cellsAtLevel = faceCount; 179 if (level > 0) { 180 cellsPerFace = 1L << (level * BIT_COUNT_PER_LEVEL); 181 cellsAtLevel *= cellsPerFace; 182 } 183 184 // Validate the offset: any offset >= the number at the cells at the level will wrap more 185 // than once and is probably a coding error. 186 if (Math.abs(offset) >= cellsAtLevel) { 187 throw new IllegalArgumentException( 188 "abs(offset) (offset=" + offset + ") > cellsAtLevel (" + cellsAtLevel + ")" 189 + " for cellId=" + cellIdToString(cellId)); 190 } 191 192 // Special case level 0 because it's easy. 193 if (level == 0) { 194 faceId += offset; 195 if (faceId < 0) { 196 faceId += faceCount; 197 } else if (faceId > MAX_FACE_ID) { 198 faceId -= faceCount; 199 } 200 long facePlusTrailingBit = faceId << 1 | 1; 201 return (facePlusTrailingBit) << (Long.SIZE - FACE_BIT_COUNT - 1); 202 } 203 204 // Handle the common level > 0 case. 205 206 // Handle cell ID wrapping, etc. 207 long cellIndex = getValidIndex(cellId); 208 long newCellIndex = cellIndex + offset; 209 int faceAdjustment = 0; 210 while (newCellIndex < 0) { 211 faceAdjustment--; 212 newCellIndex += cellsPerFace; 213 } 214 while (newCellIndex >= cellsPerFace) { 215 faceAdjustment++; 216 newCellIndex -= cellsPerFace; 217 } 218 219 int newFaceId = faceId + faceAdjustment; 220 if (newFaceId < 0) { 221 newFaceId += faceCount; 222 } else if (newFaceId >= faceCount) { 223 newFaceId -= faceCount; 224 } 225 return cellId(level, newFaceId, newCellIndex); 226 } 227 228 /** 229 * Returns the S2 level of the specified cell ID. If the cell ID is invalid it throws 230 * {@link IllegalArgumentException}. 231 */ getS2Level(long cellId)232 public static int getS2Level(long cellId) { 233 int trailingZeroCount = Long.numberOfTrailingZeros(cellId); 234 if (trailingZeroCount == Long.SIZE) { 235 throw new IllegalArgumentException("No trailing bit in " + cellId); 236 } 237 int cellIdBitCount = Long.SIZE - trailingZeroCount; 238 int cellIdBitCountWithoutFaceBitCount = cellIdBitCount - FACE_BIT_COUNT; 239 if (cellIdBitCountWithoutFaceBitCount % BIT_COUNT_PER_LEVEL != 1) { 240 throw new IllegalArgumentException( 241 cellId + " is not a valid cell Id, bitCount=" + cellIdBitCount); 242 } 243 return (cellIdBitCountWithoutFaceBitCount - 1) / BIT_COUNT_PER_LEVEL; 244 } 245 246 /** Returns the cell ID for the first cell for face 0 at the given level. */ getMinCellId(int s2Level)247 public static long getMinCellId(int s2Level) { 248 checkValidLevel(s2Level); 249 return MIN_CELL_ID[s2Level]; 250 } 251 252 /** Returns the cell ID for the last cell for face {@link #MAX_FACE_ID} at the given level. */ getMaxCellId(int s2Level)253 public static long getMaxCellId(int s2Level) { 254 checkValidLevel(s2Level); 255 return MAX_CELL_ID[s2Level]; 256 } 257 checkValidLevel(int s2Level)258 private static void checkValidLevel(int s2Level) { 259 if (s2Level < 0 || s2Level > MAX_S2_LEVEL) { 260 throw new IllegalArgumentException("s2Level " + s2Level + " is invalid"); 261 } 262 } 263 checkValidFaceId(int faceId)264 private static void checkValidFaceId(int faceId) { 265 if (faceId < 0 || faceId > MAX_FACE_ID) { 266 throw new IllegalArgumentException("faceId=" + faceId + " is invalid"); 267 } 268 } 269 calcMinS2CellId(int s2Level)270 private static long calcMinS2CellId(int s2Level) { 271 return cellId(s2Level, 0, 0); 272 } 273 calcMaxS2CellId(int s2Level)274 private static long calcMaxS2CellId(int s2Level) { 275 long maxIndex = getMaxIndex(s2Level); 276 return cellId(s2Level, MAX_FACE_ID, maxIndex); 277 } 278 } 279