diff options
Diffstat (limited to 'openbsc/src/arfcn_list_range.c')
| -rw-r--r-- | openbsc/src/arfcn_list_range.c | 194 |
1 files changed, 194 insertions, 0 deletions
diff --git a/openbsc/src/arfcn_list_range.c b/openbsc/src/arfcn_list_range.c new file mode 100644 index 000000000..b7f6e0ffd --- /dev/null +++ b/openbsc/src/arfcn_list_range.c @@ -0,0 +1,194 @@ +/* C-Implementation of the Algorithm described in Appendix J of GSM TS 44.018,
+ * (C) 2009 by Dirk Hakkesteegt <dirk@hakkesteegt.org>
+ *
+ * All Rights Reserved
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+/* Annex J.3 indicates that at least in one BA list, we can never have more
+ * than 29 frequencies within the 16byte limit */
+#define MAX_ARRFCNS 29
+
+/*****************************************************************************
+* NAME : smod
+* DESCRIPTION : n smod m indicates the offset remainder of the euclidian
+* division of n by m
+* INPUT : n, m
+* OUTPUT : n smod m
+* RETURNS :
+* Errorcodes :
+******************************************************************************/
+static int smod(int n, int m)
+{
+ int result = n % m;
+ if (result < 0)
+ result += m;
+
+ if (result == 0)
+ result = m;
+
+ return result;
+}
+
+/*****************************************************************************
+* NAME : mod
+* DESCRIPTION : n mod m indicates the remainder of the euclidian division of
+* n by m
+* INPUT : n, m
+* OUTPUT : n mod m
+* RETURNS :
+* Errorcodes :
+******************************************************************************/
+static int mod(int n, int m)
+{
+ int result = n % m;
+ if (result < 0)
+ result += m;
+
+ return result;
+}
+
+/*****************************************************************************
+* NAME : greatest_power_of_2_le_to
+* DESCRIPTION : Calculates the greatest power of 2 that is lesser or equal
+* to the input value;
+* INPUT :
+* OUTPUT :
+* RETURNS :
+* Errorcodes :
+******************************************************************************/
+static int greatest_power_of_2_le_to(int input)
+{
+ int check_val = 1;
+ while (check_val <= input)
+ check_val *= 2;
+
+ return check_val / 2;
+}
+
+/*****************************************************************************
+* NAME : ENCODE_SUBTREE
+* DESCRIPTION : Recursive encoding routine based on 3GPP TS44.018 Annex J.4
+* INPUT : index: current position in the W list
+* set: the array to be encoded
+* range: the current range
+* set_size: number of elements in set
+* OUTPUT : W: the array of results
+* RETURNS :
+* Errorcodes :
+******************************************************************************/
+static void encode_subtree(int index, int *set, int range, int set_size, int *W)
+{
+ int index_in_set = 0;
+ int N, J, I, x;
+ int subset[18];
+ int subset_index, origin_value;
+
+ /* Check if this is a leaf */
+ if (set_size == 0) {
+ W[index] = 0;
+ return;
+ } else {
+ if (set_size == 1) {
+ W[index] = 1 + set[1];
+ return;
+ }
+ }
+
+ for (I = 1; I <= set_size; I++) {
+ N = 0;
+ for (J = 1; J <= set_size; J++) {
+ x = set[J] - set[I];
+ x = mod(x, range);
+ if (x <= (range-1)/2)
+ N++;
+ }
+ if (N-1 == (set_size-1) / 2) {
+ index_in_set = I;
+ break;
+ }
+ }
+
+ W[index] = set[index_in_set] + 1;
+
+ /* Left subset */
+ subset[0] = 0;
+ origin_value = mod((set[index_in_set] + (range-1) / 2 + 1), range);
+ subset_index = 1;
+ for (I = 1; I <= set_size; I++) {
+ if (mod((set[I]-origin_value), range) < range/2) {
+ subset[subset_index] = mod((set[I] - origin_value), range);
+ subset_index++;
+ subset[subset_index] = 0;
+ }
+ }
+ encode_subtree(index + greatest_power_of_2_le_to(index),
+ subset, range / 2, subset_index-1, W);
+
+ /* Right subset */
+ subset[0] = 0;
+ origin_value = mod((set[index_in_set] + 1), range);
+ subset_index=1;
+ for (I = 1; I<= set_size; I++) {
+ if (mod((set[I]-origin_value), range) < range/2) {
+ subset[subset_index] = mod((set[I] - origin_value), range);
+ subset_index++;
+ subset[subset_index] = 0;
+ }
+ }
+ encode_subtree(index + 2*greatest_power_of_2_le_to(index),
+ subset, (range-1)/2, subset_index-1, W);
+}
+
+/*****************************************************************************
+* NAME : CalcARFCN
+* DESCRIPTION : Calculate the ARFCN list
+* INPUT : F: the list of input frequencies. MUST BE SORTED!
+* count: the number of elements in the F list
+* range: the encoding range (default: range 512)
+* OUTPUT : W: the list of W values
+* RETURNS :
+* Errorcodes :
+******************************************************************************/
+static void CalcARFCN(const unsigned int *F, int *W, unsigned int count, unsigned int range)
+{
+ int i;
+ int Fd[MAX_ARFCNS+1];
+
+ W[0] = F[0];
+ for (i = 1; i < count; i++) {
+ Fd[i] = F[i] - F[0] - 1;
+ }
+ encode_subtree(1, Fd, range-1, count-1, W);
+}
+
+int bitvec2arfcn_list_range(uint8_t *range, struct bitvec *bv, uint16_t range)
+{
+ unsigned int i, idx = 0;
+ int F[MAX_ARFCNS+1];
+ int W[MAX_ARFCNS+1];
+
+ /* build an array of integers from the bitmask */
+ for (i = 0; i < bv->data_len*8; i++) {
+ if (bitvec_get_bit_pos(bv, i))
+ F[idx++] = i;
+ }
+ /* Perform the actual algorithm to calculate the 'W' values */
+ CalcARFCN(F, W, idx, range);
+
+ /* FIXME: Encode the 'W' values into the actual format as used in 04.08 */
+
+ return -EIO;
+}
|