From 511f9c3e4a0a7ebb6294d6a2e4ac29dbcdad818c Mon Sep 17 00:00:00 2001 From: Holger Hans Peter Freyther Date: Sat, 13 Oct 2012 12:38:54 +0200 Subject: si: Partially implement the range encoding for the SI. I saw the old copy of the "Appendix J" code too late and I have discovered some quirks and I am more familar with my implementation. Most noticable 'w' only needs to be as big as the input arfcn but requires the 'w' to be initialized. The power_of_2 implementation differs as well (mine matches the output of wirehsark). The f0 could be chosen in a better way but right now picking the lower bound is the easiest. It is not clear if to use modulo if the range is chosen in the middle. This can be improved in the future. Right now I have no bit fiddling for range128, 256 and 1024 as I was running out of time. --- openbsc/src/arfcn_list_range.c | 194 ----------------------------------------- 1 file changed, 194 deletions(-) delete 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 deleted file mode 100644 index b7f6e0ffd..000000000 --- a/openbsc/src/arfcn_list_range.c +++ /dev/null @@ -1,194 +0,0 @@ -/* 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