Holger Hans Peter Freyther | 3a96d28 | 2016-04-29 21:24:48 +0200 | [diff] [blame] | 1 | #!/usr/bin/python2 |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 2 | |
| 3 | mod_license = """ |
| 4 | /* |
| 5 | * Copyright (C) 2011-2016 Sylvain Munaut <tnt@246tNt.com> |
| 6 | * Copyright (C) 2016 sysmocom s.f.m.c. GmbH |
| 7 | * |
| 8 | * All Rights Reserved |
| 9 | * |
| 10 | * This program is free software; you can redistribute it and/or modify |
| 11 | * it under the terms of the GNU General Public License as published by |
| 12 | * the Free Software Foundation; either version 3 of the License, or |
| 13 | * (at your option) any later version. |
| 14 | * |
| 15 | * This program is distributed in the hope that it will be useful, |
| 16 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 17 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 18 | * GNU General Public License for more details. |
| 19 | * |
| 20 | * You should have received a copy of the GNU General Public License along |
| 21 | * with this program; if not, write to the Free Software Foundation, Inc., |
| 22 | * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. |
| 23 | */ |
| 24 | """ |
| 25 | |
| 26 | import sys, os, math |
Vadim Yanitskiy | f9c2c56 | 2016-11-01 22:19:28 +0700 | [diff] [blame] | 27 | from functools import reduce |
Vadim Yanitskiy | 15492bc | 2016-11-10 17:10:42 +0700 | [diff] [blame] | 28 | import conv_codes_gsm |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 29 | |
| 30 | class ConvolutionalCode(object): |
| 31 | |
Vadim Yanitskiy | e31cf80 | 2016-09-07 21:51:25 +0700 | [diff] [blame] | 32 | def __init__(self, block_len, polys, name, |
Vadim Yanitskiy | a6b5216 | 2016-09-08 22:06:07 +0700 | [diff] [blame] | 33 | description = None, puncture = [], term_type = None): |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 34 | # Save simple params |
| 35 | self.block_len = block_len |
| 36 | self.k = 1 |
| 37 | self.puncture = puncture |
| 38 | self.rate_inv = len(polys) |
Vadim Yanitskiy | a6b5216 | 2016-09-08 22:06:07 +0700 | [diff] [blame] | 39 | self.term_type = term_type |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 40 | |
| 41 | # Infos |
| 42 | self.name = name |
| 43 | self.description = description |
| 44 | |
Vadim Yanitskiy | 84fc2ce | 2016-09-08 20:30:36 +0700 | [diff] [blame] | 45 | # Handle polynomials (and check for recursion) |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 46 | self.polys = [(1, 1) if x[0] == x[1] else x for x in polys] |
| 47 | |
| 48 | # Determine the polynomial degree |
| 49 | for (x, y) in polys: |
| 50 | self.k = max(self.k, int(math.floor(math.log(max(x, y), 2)))) |
| 51 | self.k = self.k + 1 |
| 52 | |
| 53 | self.poly_divider = 1 |
| 54 | rp = [x[1] for x in self.polys if x[1] != 1] |
| 55 | if rp: |
| 56 | if not all([x == rp[0] for x in rp]): |
Vadim Yanitskiy | 84fc2ce | 2016-09-08 20:30:36 +0700 | [diff] [blame] | 57 | raise ValueError("Bad polynomials: " |
| 58 | "Can't have multiple different divider polynomials!") |
Vadim Yanitskiy | e31cf80 | 2016-09-07 21:51:25 +0700 | [diff] [blame] | 59 | |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 60 | if not all([x[0] == 1 for x in polys if x[1] == 1]): |
Vadim Yanitskiy | 84fc2ce | 2016-09-08 20:30:36 +0700 | [diff] [blame] | 61 | raise ValueError("Bad polynomials: " |
Vadim Yanitskiy | e31cf80 | 2016-09-07 21:51:25 +0700 | [diff] [blame] | 62 | "Can't have a '1' divider with a non '1' dividend " |
| 63 | "in a recursive code") |
| 64 | |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 65 | self.poly_divider = rp[0] |
| 66 | |
| 67 | @property |
| 68 | def recursive(self): |
| 69 | return self.poly_divider != 1 |
| 70 | |
| 71 | @property |
| 72 | def _state_mask(self): |
| 73 | return (1 << (self.k - 1)) - 1 |
| 74 | |
| 75 | def next_state(self, state, bit): |
| 76 | nb = combine( |
| 77 | (state << 1) | bit, |
| 78 | self.poly_divider, |
| 79 | self.k, |
| 80 | ) |
| 81 | return ((state << 1) | nb) & self._state_mask |
| 82 | |
| 83 | def next_term_state(self, state): |
| 84 | return (state << 1) & self._state_mask |
| 85 | |
| 86 | def next_output(self, state, bit, ns = None): |
| 87 | # Next state bit |
| 88 | if ns is None: |
| 89 | ns = self.next_state(state, bit) |
| 90 | |
| 91 | src = (ns & 1) | (state << 1) |
| 92 | |
Vadim Yanitskiy | 84fc2ce | 2016-09-08 20:30:36 +0700 | [diff] [blame] | 93 | # Scan polynomials |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 94 | rv = [] |
| 95 | for p_n, p_d in self.polys: |
| 96 | if self.recursive and p_d == 1: |
Vadim Yanitskiy | e31cf80 | 2016-09-07 21:51:25 +0700 | [diff] [blame] | 97 | # No choice ... (systematic output in recursive case) |
| 98 | o = bit |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 99 | else: |
| 100 | o = combine(src, p_n, self.k) |
| 101 | rv.append(o) |
| 102 | |
| 103 | return rv |
| 104 | |
| 105 | def next_term_output(self, state, ns = None): |
| 106 | # Next state bit |
| 107 | if ns is None: |
| 108 | ns = self.next_term_state(state) |
| 109 | |
| 110 | src = (ns & 1) | (state << 1) |
| 111 | |
Vadim Yanitskiy | 84fc2ce | 2016-09-08 20:30:36 +0700 | [diff] [blame] | 112 | # Scan polynomials |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 113 | rv = [] |
| 114 | for p_n, p_d in self.polys: |
| 115 | if self.recursive and p_d == 1: |
| 116 | # Systematic output are replaced when in 'termination' mode |
| 117 | o = combine(src, self.poly_divider, self.k) |
| 118 | else: |
| 119 | o = combine(src, p_n, self.k) |
| 120 | rv.append(o) |
| 121 | |
| 122 | return rv |
| 123 | |
| 124 | def next(self, state, bit): |
| 125 | ns = self.next_state(state, bit) |
| 126 | nb = self.next_output(state, bit, ns = ns) |
| 127 | return ns, nb |
| 128 | |
| 129 | def next_term(self, state): |
| 130 | ns = self.next_term_state(state) |
| 131 | nb = self.next_term_output(state, ns = ns) |
| 132 | return ns, nb |
| 133 | |
Vadim Yanitskiy | e31cf80 | 2016-09-07 21:51:25 +0700 | [diff] [blame] | 134 | def _print_term(self, fi, num_states, pack = False): |
Vadim Yanitskiy | 6908fa7 | 2016-09-07 22:34:53 +0700 | [diff] [blame] | 135 | items = [] |
| 136 | |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 137 | for state in range(num_states): |
Vadim Yanitskiy | e31cf80 | 2016-09-07 21:51:25 +0700 | [diff] [blame] | 138 | if pack: |
| 139 | x = pack(self.next_term_output(state)) |
| 140 | else: |
| 141 | x = self.next_term_state(state) |
| 142 | |
Vadim Yanitskiy | 6908fa7 | 2016-09-07 22:34:53 +0700 | [diff] [blame] | 143 | items.append(x) |
| 144 | |
| 145 | # Up to 12 numbers should be placed per line |
| 146 | print_formatted(items, "%3d, ", 12, fi) |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 147 | |
| 148 | def _print_x(self, fi, num_states, pack = False): |
Vadim Yanitskiy | 6908fa7 | 2016-09-07 22:34:53 +0700 | [diff] [blame] | 149 | items = [] |
| 150 | |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 151 | for state in range(num_states): |
Vadim Yanitskiy | e31cf80 | 2016-09-07 21:51:25 +0700 | [diff] [blame] | 152 | if pack: |
| 153 | x0 = pack(self.next_output(state, 0)) |
| 154 | x1 = pack(self.next_output(state, 1)) |
| 155 | else: |
| 156 | x0 = self.next_state(state, 0) |
| 157 | x1 = self.next_state(state, 1) |
| 158 | |
Vadim Yanitskiy | 6908fa7 | 2016-09-07 22:34:53 +0700 | [diff] [blame] | 159 | items.append((x0, x1)) |
| 160 | |
| 161 | # Up to 4 blocks should be placed per line |
| 162 | print_formatted(items, "{ %2d, %2d }, ", 4, fi) |
| 163 | |
| 164 | def _print_puncture(self, fi): |
| 165 | # Up to 12 numbers should be placed per line |
| 166 | print_formatted(self.puncture, "%3d, ", 12, fi) |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 167 | |
Vadim Yanitskiy | 6431add | 2016-10-29 00:00:57 +0700 | [diff] [blame] | 168 | def print_state_and_output(self, fi): |
Vadim Yanitskiy | e31cf80 | 2016-09-07 21:51:25 +0700 | [diff] [blame] | 169 | pack = lambda n: \ |
| 170 | sum([x << (self.rate_inv - i - 1) for i, x in enumerate(n)]) |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 171 | num_states = 1 << (self.k - 1) |
Vadim Yanitskiy | e31cf80 | 2016-09-07 21:51:25 +0700 | [diff] [blame] | 172 | |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 173 | fi.write("static const uint8_t %s_state[][2] = {\n" % self.name) |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 174 | self._print_x(fi, num_states) |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 175 | fi.write("};\n\n") |
| 176 | |
| 177 | fi.write("static const uint8_t %s_output[][2] = {\n" % self.name) |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 178 | self._print_x(fi, num_states, pack) |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 179 | fi.write("};\n\n") |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 180 | |
| 181 | if self.recursive: |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 182 | fi.write("static const uint8_t %s_term_state[] = {\n" % self.name) |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 183 | self._print_term(fi, num_states) |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 184 | fi.write("};\n\n") |
Vadim Yanitskiy | e31cf80 | 2016-09-07 21:51:25 +0700 | [diff] [blame] | 185 | |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 186 | fi.write("static const uint8_t %s_term_output[] = {\n" % self.name) |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 187 | self._print_term(fi, num_states, pack) |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 188 | fi.write("};\n\n") |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 189 | |
Vadim Yanitskiy | 6431add | 2016-10-29 00:00:57 +0700 | [diff] [blame] | 190 | def gen_tables(self, pref, fi, shared_tables = None): |
| 191 | # Do not print shared tables |
| 192 | if shared_tables is None: |
| 193 | self.print_state_and_output(fi) |
| 194 | table_pref = self.name |
| 195 | else: |
| 196 | table_pref = shared_tables |
| 197 | |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 198 | if len(self.puncture): |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 199 | fi.write("static const int %s_puncture[] = {\n" % self.name) |
Vadim Yanitskiy | 6908fa7 | 2016-09-07 22:34:53 +0700 | [diff] [blame] | 200 | self._print_puncture(fi) |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 201 | fi.write("};\n\n") |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 202 | |
Vadim Yanitskiy | e31cf80 | 2016-09-07 21:51:25 +0700 | [diff] [blame] | 203 | # Write description as a multi-line comment |
| 204 | if self.description is not None: |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 205 | fi.write("/**\n") |
Vadim Yanitskiy | e31cf80 | 2016-09-07 21:51:25 +0700 | [diff] [blame] | 206 | for line in self.description: |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 207 | fi.write(" * %s\n" % line) |
| 208 | fi.write(" */\n") |
Vadim Yanitskiy | e31cf80 | 2016-09-07 21:51:25 +0700 | [diff] [blame] | 209 | |
| 210 | # Print a final convolutional code definition |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 211 | fi.write("const struct osmo_conv_code %s_%s = {\n" % (pref, self.name)) |
| 212 | fi.write("\t.N = %d,\n" % self.rate_inv) |
| 213 | fi.write("\t.K = %d,\n" % self.k) |
| 214 | fi.write("\t.len = %d,\n" % self.block_len) |
Vadim Yanitskiy | 6431add | 2016-10-29 00:00:57 +0700 | [diff] [blame] | 215 | fi.write("\t.next_output = %s_output,\n" % table_pref) |
| 216 | fi.write("\t.next_state = %s_state,\n" % table_pref) |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 217 | |
Vadim Yanitskiy | a6b5216 | 2016-09-08 22:06:07 +0700 | [diff] [blame] | 218 | if self.term_type is not None: |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 219 | fi.write("\t.term = %s,\n" % self.term_type) |
| 220 | |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 221 | if self.recursive: |
Vadim Yanitskiy | 6431add | 2016-10-29 00:00:57 +0700 | [diff] [blame] | 222 | fi.write("\t.next_term_output = %s_term_output,\n" % table_pref) |
| 223 | fi.write("\t.next_term_state = %s_term_state,\n" % table_pref) |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 224 | |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 225 | if len(self.puncture): |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 226 | fi.write("\t.puncture = %s_puncture,\n" % self.name) |
| 227 | fi.write("};\n\n") |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 228 | |
| 229 | poly = lambda *args: sum([(1 << x) for x in args]) |
| 230 | |
| 231 | def combine(src, sel, nb): |
| 232 | x = src & sel |
| 233 | fn_xor = lambda x, y: x ^ y |
| 234 | return reduce(fn_xor, [(x >> n) & 1 for n in range(nb)]) |
| 235 | |
Vadim Yanitskiy | 6908fa7 | 2016-09-07 22:34:53 +0700 | [diff] [blame] | 236 | def print_formatted(items, format, count, fi): |
| 237 | counter = 0 |
| 238 | |
| 239 | # Print initial indent |
| 240 | fi.write("\t") |
| 241 | |
| 242 | for item in items: |
| 243 | if counter > 0 and counter % count == 0: |
| 244 | fi.write("\n\t") |
| 245 | |
| 246 | fi.write(format % item) |
| 247 | counter += 1 |
| 248 | |
| 249 | fi.write("\n") |
| 250 | |
Vadim Yanitskiy | 15492bc | 2016-11-10 17:10:42 +0700 | [diff] [blame] | 251 | def print_shared(fi, shared_polys): |
Vadim Yanitskiy | 6431add | 2016-10-29 00:00:57 +0700 | [diff] [blame] | 252 | for (name, polys) in shared_polys.items(): |
| 253 | # HACK |
| 254 | code = ConvolutionalCode(0, polys, name = name) |
| 255 | code.print_state_and_output(fi) |
| 256 | |
Vadim Yanitskiy | 15492bc | 2016-11-10 17:10:42 +0700 | [diff] [blame] | 257 | def generate_codes(codes, path, prefix): |
Vadim Yanitskiy | d2d9760 | 2016-09-07 22:18:10 +0700 | [diff] [blame] | 258 | # Open a new file for writing |
Vadim Yanitskiy | 15492bc | 2016-11-10 17:10:42 +0700 | [diff] [blame] | 259 | f = open(os.path.join(path, prefix + "_conv.c"), 'w') |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 260 | f.write(mod_license + "\n") |
| 261 | f.write("#include <stdint.h>\n") |
| 262 | f.write("#include <osmocom/core/conv.h>\n\n") |
Vadim Yanitskiy | 15492bc | 2016-11-10 17:10:42 +0700 | [diff] [blame] | 263 | |
| 264 | # Print shared tables first |
| 265 | if hasattr(codes, "shared_polys"): |
| 266 | print_shared(f, codes.shared_polys) |
Harald Welte | eea18a6 | 2016-04-29 15:18:35 +0200 | [diff] [blame] | 267 | |
Vadim Yanitskiy | d2d9760 | 2016-09-07 22:18:10 +0700 | [diff] [blame] | 268 | # Generate the tables one by one |
Vadim Yanitskiy | 15492bc | 2016-11-10 17:10:42 +0700 | [diff] [blame] | 269 | for code in codes.conv_codes: |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 270 | sys.stderr.write("Generate '%s' definition\n" % code.name) |
Vadim Yanitskiy | 6431add | 2016-10-29 00:00:57 +0700 | [diff] [blame] | 271 | |
| 272 | # Check whether shared polynomials are used |
| 273 | shared = None |
Vadim Yanitskiy | 15492bc | 2016-11-10 17:10:42 +0700 | [diff] [blame] | 274 | if hasattr(codes, "shared_polys"): |
| 275 | for (name, polys) in codes.shared_polys.items(): |
| 276 | if code.polys == polys: |
| 277 | shared = name |
| 278 | break |
Vadim Yanitskiy | 6431add | 2016-10-29 00:00:57 +0700 | [diff] [blame] | 279 | |
| 280 | code.gen_tables(prefix, f, shared_tables = shared) |
Vadim Yanitskiy | d2d9760 | 2016-09-07 22:18:10 +0700 | [diff] [blame] | 281 | |
Vadim Yanitskiy | 15492bc | 2016-11-10 17:10:42 +0700 | [diff] [blame] | 282 | if __name__ == '__main__': |
| 283 | path = sys.argv[1] if len(sys.argv) > 1 else os.getcwd() |
| 284 | |
| 285 | sys.stderr.write("Generating convolutional codes...\n") |
| 286 | |
| 287 | # Generate GSM specific codes |
| 288 | generate_codes(conv_codes_gsm, path, "gsm0503") |
| 289 | |
Vadim Yanitskiy | 45ebc52 | 2016-10-27 02:19:37 +0700 | [diff] [blame] | 290 | sys.stderr.write("Generation complete.\n") |