summaryrefslogtreecommitdiffstats
path: root/openbsc/src/libbsc/arfcn_range_encode.c
blob: e67bf0a703ad08d673e26480977555e40bc9f9f6 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
/* gsm 04.08 system information (si) encoding and decoding
 * 3gpp ts 04.08 version 7.21.0 release 1998 / etsi ts 100 940 v7.21.0 */

/*
 * (C) 2012 Holger Hans Peter Freyther
 * (C) 2012 by On-Waves
 * 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/>.
 */

#include <openbsc/arfcn_range_encode.h>
#include <openbsc/debug.h>

#include <osmocom/gsm/protocol/gsm_04_08.h>

#include <osmocom/core/utils.h>

int greatest_power_of_2_lesser_or_equal_to(int index)
{
	int power_of_2 = 1;

	do {
		power_of_2 *= 2;
	} while (power_of_2 <= index);

	/* now go back one step */
	return power_of_2 / 2;
}

static inline int mod(int data, int range)
{
	int res = data % range;
	while (res < 0)
		res += range;
	return res;
}

/**
 * Determine at which index to split the ARFCNs to create an
 * equally size partition for the given range. Return -1 if
 * no such partition exists.
 */
int range_enc_find_index(const int range, const int *freqs, const int size)
{
	int i, j, n;

	const int RANGE_DELTA = (range - 1) / 2;

	for (i = 0; i < size; ++i) {
		n = 0;
		for (j = 0; j < size; ++j) {
			if (mod(freqs[j] - freqs[i], range) <= RANGE_DELTA)
				n += 1;
		}

		if (n - 1 == (size - 1) / 2)
			return i;
	}

	return -1;
}

/**
 * Range encode the ARFCN list.
 * \param range The range to use.
 * \param arfcns The list of ARFCNs
 * \param size The size of the list of ARFCNs
 * \param out Place to store the W(i) output.
 */
int range_enc_arfcns(const int range,
		const int *arfcns, int size, int *out,
		const int index)
{
	int split_at;
	int i;

	/*
	 * The below is a GNU extension and we can remove it when
	 * we move to a quicksort like in-situ swap with the pivot.
	 */
	int arfcns_left[size / 2];
	int arfcns_right[size / 2];
	int l_size;
	int r_size;
	int l_origin;
	int r_origin;


	/* Test the two recursion anchors and stop processing */
	if (size == 0)
		return 0;

	if (size == 1) {
		out[index] = 1 + arfcns[0];
		return 0;
	}

	/* Now do the processing */
	split_at = range_enc_find_index(range, arfcns, size);

	/* we now know where to split */
	out[index] = 1 + arfcns[split_at];

	/* calculate the work that needs to be done for the leafs */
	l_origin = mod(arfcns[split_at] + ((range - 1) / 2) + 1, range);
	r_origin = mod(arfcns[split_at] + 1, range);
	for (i = 0, l_size = 0, r_size = 0; i < size; ++i) {
		if (mod(arfcns[i] - l_origin, range) < range / 2)
			arfcns_left[l_size++] = mod(arfcns[i] - l_origin, range);
		if (mod(arfcns[i] - r_origin, range) < range / 2)
			arfcns_right[r_size++] = mod(arfcns[i] - r_origin, range);
	}

	/*
	 * Now recurse and we need to make this iterative... but as the
	 * tree is balanced the stack will not be too deep.
	 */
	range_enc_arfcns(range / 2, arfcns_left, l_size,
			out, index + greatest_power_of_2_lesser_or_equal_to(index + 1));
	range_enc_arfcns((range -1 ) / 2, arfcns_right, r_size,
			 out, index + (2 * greatest_power_of_2_lesser_or_equal_to(index + 1)));
	return 0;
}

/*
 * The easiest is to use f0 == arfcns[0]. This means that under certain
 * circumstances we can encode less ARFCNs than possible with an optimal f0.
 *
 * TODO: Solve the optimisation problem and pick f0 so that the max distance
 * is the smallest. Taking into account the modulo operation. I think picking
 * size/2 will be the optimal arfcn.
 */
/**
 * This implements the range determination as described in GSM 04.08 J4. The
 * result will be a base frequency f0 and the range to use. Note that for range
 * 1024 encoding f0 always refers to ARFCN 0 even if it is not an element of
 * the arfcns list.
 *
 * \param[in] arfcns The input frequencies, they must be sorted, lowest number first
 * \param[in] size The length of the array
 * \param[out] f0 The selected F0 base frequency. It might not be inside the list
 */
int range_enc_determine_range(const int *arfcns, const int size, int *f0)
{
	int max = 0;

	/*
	 * Go for the easiest. And pick arfcns[0] == f0.
	 */
	max = arfcns[size - 1] - arfcns[0];
	*f0 = arfcns[0];

	if (max < 128 && size <= 29)
		return ARFCN_RANGE_128;
	if (max < 256 && size <= 22)
		return ARFCN_RANGE_256;
	if (max < 512 && size <= 18)
		return ARFCN_RANGE_512;
	if (max < 1024 && size <= 17) {
		*f0 = 0;
		return ARFCN_RANGE_1024;
	}

	return ARFCN_RANGE_INVALID;
}

static void write_orig_arfcn(uint8_t *chan_list, int f0)
{
	chan_list[0] |= (f0 >> 9) & 1;
	chan_list[1] = (f0 >> 1);
	chan_list[2] = (f0 & 1) << 7;
}

static void write_all_wn(uint8_t *chan_list, int bit_offs,
			 int *w, int w_size, int w1_len)
{
	int octet_offs = 0; /* offset into chan_list */
	int wk_len = w1_len; /* encoding size in bits of w[k] */
	int k; /* 1 based */
	int level = 0; /* tree level, top level = 0 */
	int lvl_left = 1; /* nodes per tree level */

	/* W(2^i) to W(2^(i+1)-1) are on w1_len-i bits when present */

	for (k = 1; k <= w_size; k++) {
		int wk_left = wk_len;
		DEBUGP(DRR,
		       "k=%d, wk_len=%d, offs=%d:%d, level=%d, "
		       "lvl_left=%d\n",
		       k, wk_len, octet_offs, bit_offs, level, lvl_left);

		while (wk_left > 0) {
			int cur_bits = 8 - bit_offs;
			int cur_mask;
			int wk_slice;

			if (cur_bits > wk_left)
				cur_bits = wk_left;

			cur_mask = ((1 << cur_bits) - 1);

			DEBUGP(DRR,
			       " wk_left=%d, cur_bits=%d, offs=%d:%d\n",
			       wk_left, cur_bits, octet_offs, bit_offs);

			/* advance */
			wk_left -= cur_bits;
			bit_offs += cur_bits;

			/* right aligned wk data for current out octet */
			wk_slice = (w[k-1] >> wk_left) & cur_mask;

			/* cur_bits now contains the number of bits
			 * that are to be copied from wk to the chan_list.
			 * wk_left is set to the number of bits that must
			 * not yet be copied.
			 * bit_offs points after the bit area that is going to
			 * be overwritten:
			 *
			 *          wk_left
			 *             |
			 *             v
			 * wk: WWWWWWWWWWW
			 *        |||||<-- wk_slice, cur_bits=5
			 *      --WWWWW-
			 *             ^
			 *             |
			 *           bit_offs
			 */

			DEBUGP(DRR,
			       " wk=%02x, slice=%02x/%02x, cl=%02x\n",
			       w[k-1], wk_slice, cur_mask, wk_slice << (8 - bit_offs));

			chan_list[octet_offs] &= ~(cur_mask << (8 - bit_offs));
			chan_list[octet_offs] |= wk_slice << (8 - bit_offs);

			/* adjust output */
			if (bit_offs == 8) {
				bit_offs = 0;
				octet_offs += 1;
			}
		}

		/* adjust bit sizes */
		lvl_left -= 1;
		if (!lvl_left) {
			/* completed tree level, advance to next */
			level += 1;
			lvl_left = 1 << level;
			wk_len -= 1;
		}
	}
}

int range_enc_range128(uint8_t *chan_list, int f0, int *w)
{
	chan_list[0] = 0x8C;
	write_orig_arfcn(chan_list, f0);

	write_all_wn(&chan_list[2], 1, w, 28, 7);
	return 0;
}

int range_enc_range256(uint8_t *chan_list, int f0, int *w)
{
	chan_list[0] = 0x8A;
	write_orig_arfcn(chan_list, f0);

	write_all_wn(&chan_list[2], 1, w, 21, 8);
	return 0;
}

int range_enc_range512(uint8_t *chan_list, int f0, int *w)
{
	chan_list[0] = 0x88;
	write_orig_arfcn(chan_list, f0);

	write_all_wn(&chan_list[2], 1, w, 17, 9);
	return 0;
}

int range_enc_range1024(uint8_t *chan_list, int f0, int f0_included, int *w)
{
	chan_list[0] = 0x80 | (f0_included << 2);

	write_all_wn(&chan_list[0], 6, w, 16, 10);
	return 0;
}

int range_enc_filter_arfcns(int *arfcns,
			    const int size, const int f0, int *f0_included)
{
	int i, j = 0;
	*f0_included = 0;

	for (i = 0; i < size; ++i) {
		/*
		 * Appendix J.4 says the following:
		 * All frequencies except F(0), minus F(0) + 1.
		 * I assume we need to exclude it here.
		 */
		if (arfcns[i] == f0) {
			*f0_included = 1;
			continue;
		}

		arfcns[j++] = mod(arfcns[i] - (f0 + 1), 1024);
	}

	return j;
}