1 /*
2 * Copyright (c) 2007 - 2015 Joseph Gaeddert
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 * THE SOFTWARE.
21 */
22
23 //
24 // interleaver_create.c
25 //
26 // Create and initialize interleaver objects
27 //
28
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include <string.h>
32 #include <math.h>
33
34 #include "liquid.internal.h"
35
36 //
37 // internal methods
38 //
39
40 // permute one iteration
41 void interleaver_permute(unsigned char * _x,
42 unsigned int _n,
43 unsigned int _M,
44 unsigned int _N);
45
46 // permute one iteration (soft bit input)
47 void interleaver_permute_soft(unsigned char * _x,
48 unsigned int _n,
49 unsigned int _M,
50 unsigned int _N);
51
52 // permute one iteration with mask
53 void interleaver_permute_mask(unsigned char * _x,
54 unsigned int _n,
55 unsigned int _M,
56 unsigned int _N,
57 unsigned char _mask);
58
59 // permute one iteration (soft bit input) with mask
60 void interleaver_permute_mask_soft(unsigned char * _x,
61 unsigned int _n,
62 unsigned int _M,
63 unsigned int _N,
64 unsigned char _mask);
65
66
67 // structured interleaver object
68 struct interleaver_s {
69 unsigned int n; // number of bytes
70
71 unsigned int M; // row dimension
72 unsigned int N; // col dimension
73
74 // interleaving depth (number of permutations)
75 unsigned int depth;
76 };
77
78 // create interleaver of length _n input/output bytes
interleaver_create(unsigned int _n)79 interleaver interleaver_create(unsigned int _n)
80 {
81 interleaver q = (interleaver) malloc(sizeof(struct interleaver_s));
82 q->n = _n;
83
84 // set internal properties
85 q->depth = 4; // default depth to maximum
86
87 // compute block dimensions
88 q->M = 1 + (unsigned int) floorf(sqrtf(q->n));
89
90 q->N = q->n / q->M;
91 while (q->n >= (q->M*q->N)) q->N++; // ensures M*N >= n
92
93 return q;
94 }
95
96 // destroy interleaver object
interleaver_destroy(interleaver _q)97 void interleaver_destroy(interleaver _q)
98 {
99 // free main object memory
100 free(_q);
101 }
102
103 // print interleaver internals
interleaver_print(interleaver _q)104 void interleaver_print(interleaver _q)
105 {
106 printf("interleaver [block, %u bytes] :\n", _q->n);
107 printf(" M : %u\n", _q->M);
108 printf(" N : %u\n", _q->N);
109 printf(" depth : %u\n", _q->depth);
110 }
111
112 // set depth (number of internal iterations)
interleaver_set_depth(interleaver _q,unsigned int _depth)113 void interleaver_set_depth(interleaver _q,
114 unsigned int _depth)
115 {
116 _q->depth = _depth;
117 }
118
119 // execute forward interleaver (encoder)
120 // _q : interleaver object
121 // _msg_dec : decoded (un-interleaved) message
122 // _msg_enc : encoded (interleaved) message
interleaver_encode(interleaver _q,unsigned char * _msg_dec,unsigned char * _msg_enc)123 void interleaver_encode(interleaver _q,
124 unsigned char * _msg_dec,
125 unsigned char * _msg_enc)
126 {
127 // copy data to output
128 memmove(_msg_enc, _msg_dec, _q->n);
129
130 if (_q->depth > 0) interleaver_permute(_msg_enc, _q->n, _q->M, _q->N);
131 if (_q->depth > 1) interleaver_permute_mask(_msg_enc, _q->n, _q->M, _q->N+2, 0x0f);
132 if (_q->depth > 2) interleaver_permute_mask(_msg_enc, _q->n, _q->M, _q->N+4, 0x55);
133 if (_q->depth > 3) interleaver_permute_mask(_msg_enc, _q->n, _q->M, _q->N+8, 0x33);
134 }
135
136 // execute forward interleaver (encoder) on soft bits
137 // _q : interleaver object
138 // _msg_dec : decoded (un-interleaved) message
139 // _msg_enc : encoded (interleaved) message
interleaver_encode_soft(interleaver _q,unsigned char * _msg_dec,unsigned char * _msg_enc)140 void interleaver_encode_soft(interleaver _q,
141 unsigned char * _msg_dec,
142 unsigned char * _msg_enc)
143 {
144 // copy data to output
145 memmove(_msg_enc, _msg_dec, 8*_q->n);
146
147 if (_q->depth > 0) interleaver_permute_soft(_msg_enc, _q->n, _q->M, _q->N);
148 if (_q->depth > 1) interleaver_permute_mask_soft(_msg_enc, _q->n, _q->M, _q->N+2, 0x0f);
149 if (_q->depth > 2) interleaver_permute_mask_soft(_msg_enc, _q->n, _q->M, _q->N+4, 0x55);
150 if (_q->depth > 3) interleaver_permute_mask_soft(_msg_enc, _q->n, _q->M, _q->N+8, 0x33);
151 }
152
153 // execute reverse interleaver (decoder)
154 // _q : interleaver object
155 // _msg_enc : encoded (interleaved) message
156 // _msg_dec : decoded (un-interleaved) message
interleaver_decode(interleaver _q,unsigned char * _msg_enc,unsigned char * _msg_dec)157 void interleaver_decode(interleaver _q,
158 unsigned char * _msg_enc,
159 unsigned char * _msg_dec)
160 {
161 // copy data to output
162 memmove(_msg_dec, _msg_enc, _q->n);
163
164 if (_q->depth > 3) interleaver_permute_mask(_msg_dec, _q->n, _q->M, _q->N+8, 0x33);
165 if (_q->depth > 2) interleaver_permute_mask(_msg_dec, _q->n, _q->M, _q->N+4, 0x55);
166 if (_q->depth > 1) interleaver_permute_mask(_msg_dec, _q->n, _q->M, _q->N+2, 0x0f);
167 if (_q->depth > 0) interleaver_permute(_msg_dec, _q->n, _q->M, _q->N);
168 }
169
170 // execute reverse interleaver (decoder) on soft bits
171 // _q : interleaver object
172 // _msg_enc : encoded (interleaved) message
173 // _msg_dec : decoded (un-interleaved) message
interleaver_decode_soft(interleaver _q,unsigned char * _msg_enc,unsigned char * _msg_dec)174 void interleaver_decode_soft(interleaver _q,
175 unsigned char * _msg_enc,
176 unsigned char * _msg_dec)
177 {
178 // copy data to output
179 memmove(_msg_dec, _msg_enc, 8*_q->n);
180
181 if (_q->depth > 3) interleaver_permute_mask_soft(_msg_dec, _q->n, _q->M, _q->N+8, 0x33);
182 if (_q->depth > 2) interleaver_permute_mask_soft(_msg_dec, _q->n, _q->M, _q->N+4, 0x55);
183 if (_q->depth > 1) interleaver_permute_mask_soft(_msg_dec, _q->n, _q->M, _q->N+2, 0x0f);
184 if (_q->depth > 0) interleaver_permute_soft(_msg_dec, _q->n, _q->M, _q->N);
185 }
186
187 //
188 // internal permutation methods
189 //
190
191 // permute one iteration
interleaver_permute(unsigned char * _x,unsigned int _n,unsigned int _M,unsigned int _N)192 void interleaver_permute(unsigned char * _x,
193 unsigned int _n,
194 unsigned int _M,
195 unsigned int _N)
196 {
197 unsigned int i;
198 unsigned int j;
199 unsigned int m=0;
200 unsigned int n=_n/3;
201 unsigned int n2=_n/2;
202 unsigned char tmp;
203 for (i=0; i<n2; i++) {
204 //j = m*N + n; // input
205 do {
206 j = m*_N + n; // output
207 m++;
208 if (m == _M) {
209 n = (n+1) % (_N);
210 m=0;
211 }
212 } while (j>=n2);
213
214 // swap indices
215 tmp = _x[2*j+1];
216 _x[2*j+1] = _x[2*i+0];
217 _x[2*i+0] = tmp;
218 }
219 }
220
221 // permute one iteration (soft bit input)
interleaver_permute_soft(unsigned char * _x,unsigned int _n,unsigned int _M,unsigned int _N)222 void interleaver_permute_soft(unsigned char * _x,
223 unsigned int _n,
224 unsigned int _M,
225 unsigned int _N)
226 {
227 unsigned int i;
228 unsigned int j;
229 unsigned int m=0;
230 unsigned int n=_n/3;
231 unsigned int n2=_n/2;
232 unsigned char tmp[8];
233 for (i=0; i<n2; i++) {
234 //j = m*N + n; // input
235 do {
236 j = m*_N + n; // output
237 m++;
238 if (m == _M) {
239 n = (n+1) % (_N);
240 m=0;
241 }
242 } while (j>=n2);
243
244 // swap soft bits at indices
245 memmove( tmp, &_x[8*(2*j+1)], 8);
246 memmove( &_x[8*(2*j+1)], &_x[8*(2*i+0)], 8);
247 memmove( &_x[8*(2*i+0)], tmp, 8);
248 }
249 //printf("\n");
250 }
251
252
253 // permute one iteration with mask
interleaver_permute_mask(unsigned char * _x,unsigned int _n,unsigned int _M,unsigned int _N,unsigned char _mask)254 void interleaver_permute_mask(unsigned char * _x,
255 unsigned int _n,
256 unsigned int _M,
257 unsigned int _N,
258 unsigned char _mask)
259 {
260 unsigned int i;
261 unsigned int j;
262 unsigned int m=0;
263 unsigned int n=_n/3;
264 unsigned int n2=_n/2;
265 unsigned char tmp0;
266 unsigned char tmp1;
267 for (i=0; i<n2; i++) {
268 //j = m*N + n; // input
269 do {
270 j = m*_N + n; // output
271 m++;
272 if (m == _M) {
273 n = (n+1) % (_N);
274 m=0;
275 }
276 } while (j>=n2);
277
278 // swap indices, applying mask
279 tmp0 = (_x[2*i+0] & (~_mask)) | (_x[2*j+1] & ( _mask));
280 tmp1 = (_x[2*i+0] & ( _mask)) | (_x[2*j+1] & (~_mask));
281 _x[2*i+0] = tmp0;
282 _x[2*j+1] = tmp1;
283 }
284 }
285
286 // permute one iteration (soft bit input)
interleaver_permute_mask_soft(unsigned char * _x,unsigned int _n,unsigned int _M,unsigned int _N,unsigned char _mask)287 void interleaver_permute_mask_soft(unsigned char * _x,
288 unsigned int _n,
289 unsigned int _M,
290 unsigned int _N,
291 unsigned char _mask)
292 {
293 unsigned int i;
294 unsigned int j;
295 unsigned int k;
296 unsigned int m=0;
297 unsigned int n=_n/3;
298 unsigned int n2=_n/2;
299 unsigned char tmp;
300 for (i=0; i<n2; i++) {
301 //j = m*N + n; // input
302 do {
303 j = m*_N + n; // output
304 m++;
305 if (m == _M) {
306 n = (n+1) % (_N);
307 m=0;
308 }
309 } while (j>=n2);
310
311 // swap bits matching the mask
312 for (k=0; k<8; k++) {
313 if ( (_mask >> (8-k-1)) & 0x01 ) {
314 tmp = _x[8*(2*j+1)+k];
315 _x[8*(2*j+1)+k] = _x[8*(2*i+0)+k];
316 _x[8*(2*i+0)+k] = tmp;
317 }
318 }
319 }
320 //printf("\n");
321 }
322
323