/* 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; | |
} |