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.util; 18 19 public final class BitwiseUtils { 20 21 // [0] = ...00001 22 // [1] = ...00010 23 // [63] = 10000... 24 private static final long[] SINGLE_BIT_MASK; 25 26 static { 27 SINGLE_BIT_MASK = new long[64]; 28 long bit = 1; 29 for (int i = 0; i < 64; i++) { 30 SINGLE_BIT_MASK[i] = bit; 31 bit <<= 1; 32 } 33 } 34 35 // [{How many LSB bits are 1}] = mask 36 // [0] = 00...000 37 // [1] = 00...001 38 // [2] = 00...011 39 // [3] = 00...111 40 // ... 41 // [63] = 01...111 42 // [64] = 11...111 43 private static final long[] LOW_BITS_MASK; 44 45 static { 46 LOW_BITS_MASK = new long[65]; 47 long value = 0; 48 for (int i = 0; i < 65; i++) { 49 LOW_BITS_MASK[i] = value; 50 value = (value << 1) | 1; 51 } 52 } 53 54 // [{How many MSB bits are 1}] = mask 55 // [0] = 000...00 56 // [1] = 100...00 57 // [2] = 110...00 58 // [3] = 111...00 59 // ... 60 // [63] = 111...10 61 // [64] = 111...11 62 private static final long[] HIGH_BITS_MASK; 63 64 static { 65 HIGH_BITS_MASK = new long[65]; 66 long value = ~0; 67 for (int i = 0; i < 65; i++) { 68 HIGH_BITS_MASK[64 - i] = value; 69 value <<= 1; 70 } 71 } 72 BitwiseUtils()73 private BitwiseUtils() { 74 } 75 76 /** 77 * Returns a mask covering the specified number of "low" bits. {@code bitCount} must be between 78 * 0 and 64 inclusive. An argument of zero returns a mask with no bits set. Otherwise, numbering 79 * bits from LSB = 0, this method returns bits 0 to (bitCount - 1) set to 1. 80 */ getLowBitsMask(int bitCount)81 public static long getLowBitsMask(int bitCount) { 82 if (bitCount < 0 || bitCount > 64) { 83 throw new IllegalArgumentException("bitCount " + bitCount + " out of range"); 84 } 85 // Bits | Bit pattern 86 // 1 | 000...001 87 // 2 | 000...011 88 // 3 | 000...111 89 // ... 90 // 63 | 011...111 91 // 64 | 111...111 92 return LOW_BITS_MASK[bitCount]; 93 } 94 95 /** 96 * Returns (only) the {@code highBits} set of a {@code totalBitCount} value. 97 */ getMidBitsMask(int totalBitCount, int highBitCount)98 public static long getMidBitsMask(int totalBitCount, int highBitCount) { 99 if (totalBitCount < 1 || totalBitCount > 64) { 100 throw new IllegalArgumentException("totalBitCount " + totalBitCount + " out of range"); 101 } 102 if (highBitCount < 1 || highBitCount > totalBitCount) { 103 throw new IllegalArgumentException("highBitCount " + highBitCount + " out of range"); 104 } 105 return HIGH_BITS_MASK[(64 - totalBitCount) + highBitCount] & LOW_BITS_MASK[totalBitCount]; 106 } 107 108 /** 109 * Returns the most significant {@code highBits} bits of a long. 110 */ getHighBitsMask(int bitCount)111 public static long getHighBitsMask(int bitCount) { 112 if (bitCount < 1 || bitCount > 64) { 113 throw new IllegalArgumentException("bitCount " + bitCount + " out of range"); 114 } 115 return HIGH_BITS_MASK[bitCount]; 116 } 117 118 /** Returns the least significant {@code bitCount} bits of the specified value. */ extractLowBits(int bitCount, long value)119 public static long extractLowBits(int bitCount, long value) { 120 if (bitCount < 1 || bitCount > 64) { 121 throw new IllegalArgumentException("bitCount " + bitCount + " out of range"); 122 } else if (bitCount == 64) { 123 return value; 124 } 125 long mask = getLowBitsMask(bitCount); 126 return mask & value; 127 } 128 129 /** 130 * Returns a mask with only the numbered bit set to 1. Bits are numbered from LSB = 0 to 131 * MSB = {type width - 1}. 132 */ getSingleBitMask(int bit)133 public static long getSingleBitMask(int bit) { 134 if (bit < 0 || bit > 63) { 135 throw new IllegalArgumentException("bit " + bit + " out of range"); 136 } 137 return SINGLE_BIT_MASK[bit]; 138 } 139 140 /** 141 * Throws an {@link IllegalArgumentException} if value is outside of the range representable in 142 * {@code bitCount} bits as a signed or unsigned integer. Bit count must be between 1 and 64, 143 * inclusive otherwise an {@link IllegalArgumentException} is thrown. 144 */ checkValueInRange(int bitCount, long value, boolean signedValue)145 public static void checkValueInRange(int bitCount, long value, boolean signedValue) { 146 if (signedValue) { 147 checkSignedValueInRange(bitCount, value); 148 } else { 149 checkUnsignedValueInRange(bitCount, value); 150 } 151 } 152 153 /** 154 * Throws an {@link IllegalArgumentException} if value is outside of the range representable in 155 * {@code bitCount} bits as a signed integer. Bit count must be between 1 and 64, inclusive 156 * otherwise an {@link IllegalArgumentException} is thrown. 157 */ checkSignedValueInRange(int bitCount, long value)158 public static void checkSignedValueInRange(int bitCount, long value) { 159 if (bitCount < 1 || bitCount > 64) { 160 throw new IllegalArgumentException("bitCount " + bitCount + " out of range"); 161 } 162 long minSignedValue = minSignedValue(bitCount); 163 long maxSignedValue = maxSignedValue(bitCount); 164 if (value < minSignedValue || value > maxSignedValue) { 165 throw new IllegalArgumentException("value " + value + " out of range"); 166 } 167 } 168 169 /** 170 * Throws an {@link IllegalArgumentException} if value is outside of the range representable in 171 * {@code bitCount} bits as a signed integer. Bit count must be between 1 and 64, inclusive 172 * otherwise an {@link IllegalArgumentException} is thrown. 173 */ checkUnsignedValueInRange(int bitCount, long value)174 public static void checkUnsignedValueInRange(int bitCount, long value) { 175 if (bitCount < 0 || bitCount > 63) { 176 throw new IllegalArgumentException("bitCount " + bitCount + " out of range"); 177 } 178 long maxUnsignedValue = maxUnsignedValue(bitCount); 179 if (value < 0 || value > maxUnsignedValue) { 180 throw new IllegalArgumentException("value " + value + " out of range"); 181 } 182 } 183 184 /** Sign extend the {@code value} of {@code bitCount} to be a long. */ signExtendToLong(int bitCount, long value)185 public static long signExtendToLong(int bitCount, long value) { 186 if (bitCount > 64) { 187 throw new IllegalArgumentException("bitCount " + bitCount + " out of range"); 188 } else if (bitCount == 64) { 189 return value; 190 } 191 long signBitMask = getSingleBitMask(bitCount - 1); 192 // Is sign bit set? 193 if ((signBitMask & value) == signBitMask) { 194 // Extend value to long. 195 value |= getHighBitsMask(Long.SIZE - bitCount); 196 } else { 197 // This clears bits above the sign bit. 198 value &= getLowBitsMask(bitCount); 199 } 200 return value; 201 } 202 203 /** 204 * Returns the most positive numeric value representable in {@code bitCount} when signed or 205 * unsigned. {@code bitCount} must be between 1 and 64 inclusive for signed, or 1 and 63 206 * inclusive for unsigned, or an {@link IllegalArgumentException} will be thrown. 207 */ maxValue(int bitCount, boolean signedValue)208 public static long maxValue(int bitCount, boolean signedValue) { 209 if (signedValue) { 210 return maxSignedValue(bitCount); 211 } else { 212 return maxUnsignedValue(bitCount); 213 } 214 } 215 216 /** 217 * Returns the most positive numeric value that can be represented with the specified number of 218 * bits when signed. {@code bitCount} must be between 1 and 64 inclusive or an 219 * {@link IllegalArgumentException} will be thrown. 220 * 221 * Like {@link #maxUnsignedValue(int)} but returns the answer for signed types. 222 */ maxSignedValue(int bitCount)223 public static long maxSignedValue(int bitCount) { 224 if (bitCount < 1 || bitCount > 64) { 225 throw new IllegalArgumentException("bitCount " + bitCount + " out of range"); 226 } 227 // Bits | Numeric | Bit pattern 228 // 1 | 0 | 000...000 229 // 2 | 1 | 000...001 230 // 3 | 3 | 000...011 231 // 4 | 7 | 000...111 232 // ... 233 // 64 |(2^63)-1 | 011...111 234 return LOW_BITS_MASK[bitCount - 1]; 235 } 236 237 /** 238 * Returns the most positive numeric value that can be represented with the specified number of 239 * bits when unsigned. {@code bitCount} must be between 1 and 63 inclusive or an 240 * {@link IllegalArgumentException} will be thrown. 241 * 242 * Like {@link #getLowBitsMask(int)} but intended for numeric types. 243 */ maxUnsignedValue(int bitCount)244 public static long maxUnsignedValue(int bitCount) { 245 if (bitCount < 1 || bitCount > 63) { 246 throw new IllegalArgumentException("bitCount " + bitCount + " out of range"); 247 } 248 // Bits | Numeric | Bit pattern 249 // 1 | 1 | 000...001 250 // 2 | 3 | 000...011 251 // 3 | 7 | 000...111 252 // ... 253 // 63 | (2^63) | 011...111 254 return LOW_BITS_MASK[bitCount]; 255 } 256 257 /** 258 * Returns the most negative value representable in {@code bitCount} when signed or unsigned. 259 * {@code bitCount} must be between 1 and 64 inclusive for signed, or 1 and 63 inclusive for 260 * unsigned, or an {@link IllegalArgumentException} will be thrown. 261 */ minValue(int bitCount, boolean signedValue)262 public static long minValue(int bitCount, boolean signedValue) { 263 if (signedValue) { 264 return minSignedValue(bitCount); 265 } else { 266 if (bitCount < 1 || bitCount > 63) { 267 throw new IllegalArgumentException("bitCount " + bitCount + " out of range"); 268 } 269 return 0; 270 } 271 } 272 273 /** 274 * Returns the most negative numeric value that can be represented with the specified number of 275 * bits. {@code bitCount} must be between 1 and 64 inclusive or an {@link 276 * IllegalArgumentException} will be thrown. 277 */ minSignedValue(int bitCount)278 public static long minSignedValue(int bitCount) { 279 if (bitCount < 1 || bitCount > 64) { 280 throw new IllegalArgumentException("bitCount " + bitCount + " out of range"); 281 } 282 // Bits | Numeric | Bit pattern 283 // 1 | -1 | {sign extended} 1 (64 bits) 284 // 2 | -2 | {sign extended} 10 (63 bits) 285 // 3 | -4 | {sign extended} 100 (62 bits) 286 // 4 | -8 | {sign extended} 1000 (61 bits) 287 // ... 288 // 64 | -(2^63)| 100...000 (1 bit) 289 return HIGH_BITS_MASK[65 - bitCount]; 290 } 291 292 /** 293 * Prints out a human readable binary string for {@code value}, leading-zero padded to the 294 * specified length. If {@code value} cannot be represented in {@code bitCount} characters, an 295 * {@link IllegalArgumentException} is thrown. 296 */ toUnsignedString(int bitCount, long value)297 public static String toUnsignedString(int bitCount, long value) { 298 String binaryString = Long.toBinaryString(value); 299 if (binaryString.length() > bitCount) { 300 throw new IllegalArgumentException( 301 "value=" + value + " is not representable in " + bitCount + " bits"); 302 } 303 StringBuilder builder = new StringBuilder(bitCount); 304 for (int i = 0; i < bitCount - binaryString.length(); i++) { 305 builder.append('0'); 306 } 307 builder.append(binaryString); 308 return builder.toString(); 309 } 310 } 311