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