1 /** 2 * Copyright (C) 2018 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.car.radio.bands; 18 19 import android.hardware.radio.ProgramSelector; 20 import android.hardware.radio.RadioManager.BandDescriptor; 21 22 import androidx.annotation.NonNull; 23 import androidx.annotation.Nullable; 24 25 import com.android.car.broadcastradio.support.platform.ProgramSelectorExt; 26 import com.android.car.radio.platform.RadioTunerExt; 27 import com.android.car.radio.platform.RadioTunerExt.TuneCallback; 28 import com.android.car.radio.util.Log; 29 30 import java.util.List; 31 import java.util.Random; 32 33 abstract class AMFMProgramType extends ProgramType { 34 private static final String TAG = "BcRadioApp.ProgramType"; 35 AMFMProgramType(@ypeId int id)36 AMFMProgramType(@TypeId int id) { 37 super(id); 38 } 39 getLeadingDigitsFactor()40 protected abstract int getLeadingDigitsFactor(); 41 getBands(@onNull RegionConfig config)42 private List<BandDescriptor> getBands(@NonNull RegionConfig config) { 43 return (this == ProgramType.AM) ? config.getAmConfig() : config.getFmConfig(); 44 } 45 46 @Override tuneToDefault(@onNull RadioTunerExt tuner, @NonNull RegionConfig config, @Nullable TuneCallback result)47 public void tuneToDefault(@NonNull RadioTunerExt tuner, @NonNull RegionConfig config, 48 @Nullable TuneCallback result) { 49 List<BandDescriptor> bands = getBands(config); 50 if (bands.size() == 0) { 51 Log.e(TAG, "No " + getEnglishName() + " bands provided by the hardware"); 52 return; 53 } 54 55 /* Select random initial frequency to give some fairness in picking the initial station. 56 * Please note it does not give uniform fairness for all radio stations (i.e. this 57 * algorithm is biased towards stations that have a lot of unused channels before them), 58 * but is a fair compromise between complexity and distribution. 59 */ 60 Random rnd = new Random(); 61 BandDescriptor band = bands.get(rnd.nextInt(bands.size())); 62 int freq = rnd.nextInt(band.getUpperLimit() - band.getLowerLimit()) + band.getLowerLimit(); 63 freq /= band.getSpacing(); 64 freq *= band.getSpacing(); 65 66 // tune to that frequency and seek forward, to find any station 67 tuner.tune(ProgramSelectorExt.createAmFmSelector(freq), succeeded -> { 68 if (!succeeded) { 69 result.onFinished(false); 70 return; 71 } 72 tuner.seek(true, result); 73 }); 74 } 75 76 @Override isComplete(@onNull RegionConfig config, int leadingDigits)77 public boolean isComplete(@NonNull RegionConfig config, int leadingDigits) { 78 int frequencyKhz = leadingDigits * getLeadingDigitsFactor(); 79 80 for (BandDescriptor band : getBands(config)) { 81 if (band.getLowerLimit() <= frequencyKhz && frequencyKhz <= band.getUpperLimit() 82 && (frequencyKhz - band.getLowerLimit()) % band.getSpacing() == 0) { 83 return true; 84 } 85 } 86 return false; 87 } 88 89 @Override 90 @NonNull parseDigits(int leadingDigits)91 public ProgramSelector parseDigits(int leadingDigits) { 92 return ProgramSelectorExt.createAmFmSelector(leadingDigits * getLeadingDigitsFactor()); 93 } 94 numLength(int number)95 private static int numLength(int number) { 96 if (number == 0) return 0; 97 return (int) Math.floor(Math.log10(number)) + 1; 98 } 99 divCeil(int a, int b)100 private static int divCeil(int a, int b) { 101 return ((a - 1) / b) + 1; 102 } 103 104 @Override 105 @NonNull getValidAppendices(@onNull RegionConfig config, int leadingDigits)106 public boolean[] getValidAppendices(@NonNull RegionConfig config, int leadingDigits) { 107 /* TL;DR: This algorithm iterates through all [3] channels within the range [2] to determine 108 * all valid digits on the specified index [1]. 109 * 110 * [1] The index we're checking the digits on is the next position user will add digit to 111 * the partial channel number. I.e. if he entered 88, we're looking for valid digits to add 112 * at the index 2 (88x). We need to check that for all possible channel lengths (i.e. 113 * 88.5/103.3 FM or 153/1503/12000 AM). 114 * 115 * [2] The range is limited to the actual regional frequency bounds and what the user 116 * already entered (i.e. for 8, we're checking 80.0 through 89.9). 117 * 118 * [3] It's actually optimized: instead of iterating through all channels, we maximize jumps 119 * so a single digit to add is checked at most two times. Only the n-th channel has a chance 120 * to advance the digit on next position. 121 * 122 * The complexity of this algorithm is O(n * log m * k), where: 123 * - n is the number of ranges (bands, i.e. AM SW, MW and LW); 124 * - log m is the length of 10-based channel representation; 125 * - k is the alphabet length (digits 0-9). 126 * 127 * 128 * In this algorithm, the channel is represented in three forms: 129 * - raw frequency in KHz (i.e. 88700) - denoted by KHz suffix; 130 * - display form (i.e. 887 for 88.7 MHz) - denoted by Disp suffix; 131 * - channel prefix (i.e. 8, 88 or 887) - leadingDigits variable only. 132 * 133 * All number lengths are "display length", what means it refers to the length of the 134 * display form (i.e. 3 for 88.7 MHz and 4 for 1600 kHz). 135 * 136 * Current position: the index of digit recently entered by the user. 137 * Next position: the digit index we're evaluating if it's valid to append. 138 */ 139 boolean[] digits = new boolean[10]; 140 // the factor that converts display form to raw frequency (i.e. x100 for FM, x1 for AM). 141 int displayFactor = getLeadingDigitsFactor(); 142 int curLenDisp = numLength(leadingDigits); 143 int[] pow10 = {1, 10, 100, 1_000, 10_000, 100_000, 1_000_000, 144 10_000_000, 100_000_000, 1_000_000_000}; 145 146 for (BandDescriptor band : getBands(config)) { 147 int lowerLimitKHz = band.getLowerLimit(); 148 int upperLimitKHz = band.getUpperLimit(); 149 int spacingKHz = band.getSpacing(); 150 int minLenDisp = numLength(lowerLimitKHz / displayFactor); // display length 151 int maxLenDisp = numLength(upperLimitKHz / displayFactor); 152 153 // let's try making up channels exactly of length expLenDisp 154 for (int expLenDisp = Math.max(curLenDisp + 1, minLenDisp); 155 expLenDisp <= maxLenDisp; expLenDisp++) { 156 // 1 shifted to the current digit position (recently added by the user) 157 int curPosFactor = pow10[expLenDisp - curLenDisp]; 158 // 1 shifted to the next digit position (evaluated whether is valid to append) 159 int nextPosFactor = pow10[expLenDisp - curLenDisp - 1]; 160 161 // Let's figure out the spacing jump: see [3]. 162 // first of all, set the jump to the digit we want to advance 163 int spacingJumpKHz = nextPosFactor * displayFactor; 164 // align to the spacing (so the jump will not advance next digit more than by 1) 165 spacingJumpKHz = (spacingJumpKHz / spacingKHz) * spacingKHz; 166 // if the jump is less than spacing, make it even 167 spacingJumpKHz = Math.max(spacingJumpKHz, spacingKHz); 168 169 // let's figure out the range to scan (iterate) 170 // start with the number already entered (i.e. 87 -> 87.0; 8 -> 80.0) 171 int scanStartKHz = leadingDigits * curPosFactor * displayFactor; 172 // end with the already entered number as well (i.e. 87 -> 87.999; 8 -> 89.999) 173 int scanEndKHz = (leadingDigits + 1) * curPosFactor * displayFactor - 1; 174 // filter out channels with leading zeros (087.9, if we expect 1xx.x) 175 scanStartKHz = Math.max(scanStartKHz, nextPosFactor * displayFactor); 176 // align to the first valid channel 177 int scanStartShiftKHz = Math.max(0, scanStartKHz - lowerLimitKHz); 178 scanStartShiftKHz = divCeil(scanStartShiftKHz, spacingKHz) * spacingKHz; 179 scanStartKHz = lowerLimitKHz + scanStartShiftKHz; 180 // check the bounds (start was already checked in scanStartShiftKhz definition) 181 scanEndKHz = Math.min(scanEndKHz, upperLimitKHz); 182 183 for (int channelKHz = scanStartKHz; channelKHz <= scanEndKHz; 184 channelKHz += spacingJumpKHz) { 185 int channelDisp = channelKHz / displayFactor; 186 // pick the digit from the next index 187 int nextDigit = (channelDisp % curPosFactor) / nextPosFactor; 188 189 digits[nextDigit] = true; 190 } 191 } 192 } 193 194 return digits; 195 } 196 } 197