From 9af6ddfcec25f43c5b50a6c5a6b80e341ab9a8a7 Mon Sep 17 00:00:00 2001 From: Harald Welte Date: Sat, 1 Jan 2011 15:25:50 +0100 Subject: License change: We are now AGPLv3+ instead of GPLv2+ The reason for this is quite simple: We want to make sure anyone running a customized version of OpenBSC to operate a network will have to release all custom modifiations to the source code. --- openbsc/src/arfcn_list_range.c | 194 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 194 insertions(+) create mode 100644 openbsc/src/arfcn_list_range.c (limited to 'openbsc/src/arfcn_list_range.c') 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 + * + * 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 . + * + */ +/* 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; +} -- cgit v1.2.3