Harald Welte | 9af6ddf | 2011-01-01 15:25:50 +0100 | [diff] [blame] | 1 | /* C-Implementation of the Algorithm described in Appendix J of GSM TS 44.018,
|
| 2 | * (C) 2009 by Dirk Hakkesteegt <dirk@hakkesteegt.org>
|
| 3 | *
|
| 4 | * All Rights Reserved
|
| 5 | *
|
| 6 | * This program is free software; you can redistribute it and/or modify
|
| 7 | * it under the terms of the GNU Affero General Public License as published by
|
| 8 | * the Free Software Foundation; either version 3 of the License, or
|
| 9 | * (at your option) any later version.
|
| 10 | *
|
| 11 | * This program is distributed in the hope that it will be useful,
|
| 12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
| 13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
| 14 | * GNU Affero General Public License for more details.
|
| 15 | *
|
| 16 | * You should have received a copy of the GNU Affero General Public License
|
| 17 | * along with this program. If not, see <http://www.gnu.org/licenses/>.
|
| 18 | *
|
| 19 | */
|
| 20 | /* Annex J.3 indicates that at least in one BA list, we can never have more
|
| 21 | * than 29 frequencies within the 16byte limit */
|
| 22 | #define MAX_ARRFCNS 29
|
| 23 |
|
| 24 | /*****************************************************************************
|
| 25 | * NAME : smod
|
| 26 | * DESCRIPTION : n smod m indicates the offset remainder of the euclidian
|
| 27 | * division of n by m
|
| 28 | * INPUT : n, m
|
| 29 | * OUTPUT : n smod m
|
| 30 | * RETURNS :
|
| 31 | * Errorcodes :
|
| 32 | ******************************************************************************/
|
| 33 | static int smod(int n, int m)
|
| 34 | {
|
| 35 | int result = n % m;
|
| 36 | if (result < 0)
|
| 37 | result += m;
|
| 38 |
|
| 39 | if (result == 0)
|
| 40 | result = m;
|
| 41 |
|
| 42 | return result;
|
| 43 | }
|
| 44 |
|
| 45 | /*****************************************************************************
|
| 46 | * NAME : mod
|
| 47 | * DESCRIPTION : n mod m indicates the remainder of the euclidian division of
|
| 48 | * n by m
|
| 49 | * INPUT : n, m
|
| 50 | * OUTPUT : n mod m
|
| 51 | * RETURNS :
|
| 52 | * Errorcodes :
|
| 53 | ******************************************************************************/
|
| 54 | static int mod(int n, int m)
|
| 55 | {
|
| 56 | int result = n % m;
|
| 57 | if (result < 0)
|
| 58 | result += m;
|
| 59 |
|
| 60 | return result;
|
| 61 | }
|
| 62 |
|
| 63 | /*****************************************************************************
|
| 64 | * NAME : greatest_power_of_2_le_to
|
| 65 | * DESCRIPTION : Calculates the greatest power of 2 that is lesser or equal
|
| 66 | * to the input value;
|
| 67 | * INPUT :
|
| 68 | * OUTPUT :
|
| 69 | * RETURNS :
|
| 70 | * Errorcodes :
|
| 71 | ******************************************************************************/
|
| 72 | static int greatest_power_of_2_le_to(int input)
|
| 73 | {
|
| 74 | int check_val = 1;
|
| 75 | while (check_val <= input)
|
| 76 | check_val *= 2;
|
| 77 |
|
| 78 | return check_val / 2;
|
| 79 | }
|
| 80 |
|
| 81 | /*****************************************************************************
|
| 82 | * NAME : ENCODE_SUBTREE
|
| 83 | * DESCRIPTION : Recursive encoding routine based on 3GPP TS44.018 Annex J.4
|
| 84 | * INPUT : index: current position in the W list
|
| 85 | * set: the array to be encoded
|
| 86 | * range: the current range
|
| 87 | * set_size: number of elements in set
|
| 88 | * OUTPUT : W: the array of results
|
| 89 | * RETURNS :
|
| 90 | * Errorcodes :
|
| 91 | ******************************************************************************/
|
| 92 | static void encode_subtree(int index, int *set, int range, int set_size, int *W)
|
| 93 | {
|
| 94 | int index_in_set = 0;
|
| 95 | int N, J, I, x;
|
| 96 | int subset[18];
|
| 97 | int subset_index, origin_value;
|
| 98 |
|
| 99 | /* Check if this is a leaf */
|
| 100 | if (set_size == 0) {
|
| 101 | W[index] = 0;
|
| 102 | return;
|
| 103 | } else {
|
| 104 | if (set_size == 1) {
|
| 105 | W[index] = 1 + set[1];
|
| 106 | return;
|
| 107 | }
|
| 108 | }
|
| 109 |
|
| 110 | for (I = 1; I <= set_size; I++) {
|
| 111 | N = 0;
|
| 112 | for (J = 1; J <= set_size; J++) {
|
| 113 | x = set[J] - set[I];
|
| 114 | x = mod(x, range);
|
| 115 | if (x <= (range-1)/2)
|
| 116 | N++;
|
| 117 | }
|
| 118 | if (N-1 == (set_size-1) / 2) {
|
| 119 | index_in_set = I;
|
| 120 | break;
|
| 121 | }
|
| 122 | }
|
| 123 |
|
| 124 | W[index] = set[index_in_set] + 1;
|
| 125 |
|
| 126 | /* Left subset */
|
| 127 | subset[0] = 0;
|
| 128 | origin_value = mod((set[index_in_set] + (range-1) / 2 + 1), range);
|
| 129 | subset_index = 1;
|
| 130 | for (I = 1; I <= set_size; I++) {
|
| 131 | if (mod((set[I]-origin_value), range) < range/2) {
|
| 132 | subset[subset_index] = mod((set[I] - origin_value), range);
|
| 133 | subset_index++;
|
| 134 | subset[subset_index] = 0;
|
| 135 | }
|
| 136 | }
|
| 137 | encode_subtree(index + greatest_power_of_2_le_to(index),
|
| 138 | subset, range / 2, subset_index-1, W);
|
| 139 |
|
| 140 | /* Right subset */
|
| 141 | subset[0] = 0;
|
| 142 | origin_value = mod((set[index_in_set] + 1), range);
|
| 143 | subset_index=1;
|
| 144 | for (I = 1; I<= set_size; I++) {
|
| 145 | if (mod((set[I]-origin_value), range) < range/2) {
|
| 146 | subset[subset_index] = mod((set[I] - origin_value), range);
|
| 147 | subset_index++;
|
| 148 | subset[subset_index] = 0;
|
| 149 | }
|
| 150 | }
|
| 151 | encode_subtree(index + 2*greatest_power_of_2_le_to(index),
|
| 152 | subset, (range-1)/2, subset_index-1, W);
|
| 153 | }
|
| 154 |
|
| 155 | /*****************************************************************************
|
| 156 | * NAME : CalcARFCN
|
| 157 | * DESCRIPTION : Calculate the ARFCN list
|
| 158 | * INPUT : F: the list of input frequencies. MUST BE SORTED!
|
| 159 | * count: the number of elements in the F list
|
| 160 | * range: the encoding range (default: range 512)
|
| 161 | * OUTPUT : W: the list of W values
|
| 162 | * RETURNS :
|
| 163 | * Errorcodes :
|
| 164 | ******************************************************************************/
|
| 165 | static void CalcARFCN(const unsigned int *F, int *W, unsigned int count, unsigned int range)
|
| 166 | {
|
| 167 | int i;
|
| 168 | int Fd[MAX_ARFCNS+1];
|
| 169 |
|
| 170 | W[0] = F[0];
|
| 171 | for (i = 1; i < count; i++) {
|
| 172 | Fd[i] = F[i] - F[0] - 1;
|
| 173 | }
|
| 174 | encode_subtree(1, Fd, range-1, count-1, W);
|
| 175 | }
|
| 176 |
|
| 177 | int bitvec2arfcn_list_range(uint8_t *range, struct bitvec *bv, uint16_t range)
|
| 178 | {
|
| 179 | unsigned int i, idx = 0;
|
| 180 | int F[MAX_ARFCNS+1];
|
| 181 | int W[MAX_ARFCNS+1];
|
| 182 |
|
| 183 | /* build an array of integers from the bitmask */
|
| 184 | for (i = 0; i < bv->data_len*8; i++) {
|
| 185 | if (bitvec_get_bit_pos(bv, i))
|
| 186 | F[idx++] = i;
|
| 187 | }
|
| 188 | /* Perform the actual algorithm to calculate the 'W' values */
|
| 189 | CalcARFCN(F, W, idx, range);
|
| 190 |
|
| 191 | /* FIXME: Encode the 'W' values into the actual format as used in 04.08 */
|
| 192 |
|
| 193 | return -EIO;
|
| 194 | }
|