1/* 2 * Copyright (C) 2022 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 */ 16type TypedArray = 17 | Int8Array 18 | Uint8Array 19 | Uint8ClampedArray 20 | Int16Array 21 | Uint16Array 22 | Int32Array 23 | Uint32Array 24 | Float32Array 25 | Float64Array; 26 27/** 28 * Utility functions for working with arrays. 29 */ 30export class ArrayUtils { 31 /** 32 * Checks if two arrays are equal. 33 * 34 * @param a The first array. 35 * @param b The second array. 36 * @param predicate A function that takes two elements and returns true if they are equal. Defaults to strict equality. 37 * True if the arrays are equal, false otherwise. 38 */ 39 static equal<T>( 40 a: T[] | TypedArray, 41 b: T[] | TypedArray, 42 predicate: (a: T | number, b: T | number) => boolean = (a, b) => a === b, 43 ): boolean { 44 if (a.length !== b.length) { 45 return false; 46 } 47 48 for (let i = 0; i < a.length; i++) { 49 if (!predicate(a[i], b[i])) { 50 return false; 51 } 52 } 53 54 return true; 55 } 56 57 /** 58 * Searches for a subarray within an array. 59 * 60 * @param array The array to search in. 61 * @param subarray The subarray to search for. 62 * @return The index of the first occurrence of the subarray, or undefined if it is not found. 63 */ 64 static searchSubarray<T>( 65 array: T[] | TypedArray, 66 subarray: T[] | TypedArray, 67 ): number | undefined { 68 for (let i = 0; i + subarray.length <= array.length; ++i) { 69 let match = true; 70 71 for (let j = 0; j < subarray.length; ++j) { 72 if (array[i + j] !== subarray[j]) { 73 match = false; 74 break; 75 } 76 } 77 78 if (match) { 79 return i; 80 } 81 } 82 83 return undefined; 84 } 85 86 /** 87 * Performs a binary search to find the first element in the array that is greater than or equal to the target value. 88 * 89 * @param values The array to search in. 90 * @param target The value to search for. 91 * @return The index of the first element that is greater than or equal to the target value, or undefined if no such element exists. 92 */ 93 static binarySearchFirstGreaterOrEqual<T>( 94 values: T[] | TypedArray, 95 target: T, 96 ): number | undefined { 97 if (values.length === 0) { 98 return undefined; 99 } 100 101 let low = 0; 102 let high = values.length - 1; 103 104 let result: number | undefined = undefined; 105 106 while (low <= high) { 107 const mid = (low + high) >> 1; 108 109 if (values[mid] < target) { 110 low = mid + 1; 111 } else if (values[mid] > target) { 112 if (result === undefined || result > mid) { 113 result = mid; 114 } 115 high = mid - 1; 116 } else { 117 result = mid; 118 high = mid - 1; 119 } 120 } 121 122 return result; 123 } 124 125 /** 126 * Performs a binary search to find the first element in the array that is greater than the target value. 127 * 128 * @param values The array to search in. 129 * @param target The value to search for. 130 * @return The index of the first element that is greater than the target value, or undefined if no such element exists. 131 */ 132 static binarySearchFirstGreater<T>( 133 values: T[] | TypedArray, 134 target: T, 135 ): number | undefined { 136 if (values.length === 0) { 137 return undefined; 138 } 139 140 let low = 0; 141 let high = values.length - 1; 142 143 let result: number | undefined = undefined; 144 145 while (low <= high) { 146 const mid = (low + high) >> 1; 147 148 if (values[mid] < target) { 149 low = mid + 1; 150 } else if (values[mid] > target) { 151 if (result === undefined || result > mid) { 152 result = mid; 153 } 154 high = mid - 1; 155 } else { 156 low = mid + 1; 157 } 158 } 159 160 return result; 161 } 162 163 /** 164 * Converts an array of bytes to a bigint in little-endian order. 165 * 166 * @param buffer The array of bytes to convert. 167 * @param start The starting index of the bytes to convert. 168 * @param end The ending index of the bytes to convert. 169 * @return The bigint representation of the bytes in little-endian order. 170 */ 171 static toUintLittleEndian( 172 buffer: Uint8Array, 173 start: number, 174 end: number, 175 ): bigint { 176 let result = 0n; 177 for (let i = end - 1; i >= start; --i) { 178 result *= 256n; 179 result += BigInt(buffer[i]); 180 } 181 return result; 182 } 183 184 /** 185 * Converts an array of bytes to a bigint in little-endian order, treating the bytes as a signed integer. 186 * 187 * @param buffer The array of bytes to convert. 188 * @param start The starting index of the bytes to convert. 189 * @param end The ending index of the bytes to convert. 190 * @return The bigint representation of the bytes in little-endian order, treating the bytes as a signed integer. 191 */ 192 static toIntLittleEndian( 193 buffer: Uint8Array, 194 start: number, 195 end: number, 196 ): bigint { 197 const numOfBits = BigInt(Math.max(0, 8 * (end - start))); 198 if (numOfBits <= 0n) { 199 return 0n; 200 } 201 202 let result = ArrayUtils.toUintLittleEndian(buffer, start, end); 203 const maxSignedValue = 2n ** (numOfBits - 1n) - 1n; 204 if (result > maxSignedValue) { 205 const valuesRange = 2n ** numOfBits; 206 result -= valuesRange; 207 } 208 209 return result; 210 } 211} 212