From 9e2e8358a3cd5ec0a34906e672b227a90e558306 Mon Sep 17 00:00:00 2001 From: Piotr Krysik Date: Tue, 27 Feb 2018 12:16:25 +0100 Subject: Portability fix: Adding local partial copy of libosmocore (TODO: minimize it) --- lib/decoding/osmocom/core/CMakeLists.txt | 11 + lib/decoding/osmocom/core/bit16gen.h | 105 ++++ lib/decoding/osmocom/core/bit32gen.h | 105 ++++ lib/decoding/osmocom/core/bit64gen.h | 105 ++++ lib/decoding/osmocom/core/bits.c | 311 ++++++++++++ lib/decoding/osmocom/core/bits.h | 122 +++++ lib/decoding/osmocom/core/bitvec.c | 708 ++++++++++++++++++++++++++ lib/decoding/osmocom/core/bitvec.h | 87 ++++ lib/decoding/osmocom/core/conv.c | 644 ++++++++++++++++++++++++ lib/decoding/osmocom/core/conv.h | 139 ++++++ lib/decoding/osmocom/core/conv_acc.c | 720 +++++++++++++++++++++++++++ lib/decoding/osmocom/core/conv_acc_generic.c | 213 ++++++++ lib/decoding/osmocom/core/crc16gen.c | 120 +++++ lib/decoding/osmocom/core/crc16gen.h | 56 +++ lib/decoding/osmocom/core/crc32gen.h | 56 +++ lib/decoding/osmocom/core/crc64gen.c | 120 +++++ lib/decoding/osmocom/core/crc64gen.h | 56 +++ lib/decoding/osmocom/core/crc8gen.c | 120 +++++ lib/decoding/osmocom/core/crc8gen.h | 56 +++ lib/decoding/osmocom/core/crcgen.h | 34 ++ lib/decoding/osmocom/core/defs.h | 53 ++ lib/decoding/osmocom/core/endian.h | 62 +++ lib/decoding/osmocom/core/linuxlist.h | 409 +++++++++++++++ lib/decoding/osmocom/core/panic.c | 100 ++++ lib/decoding/osmocom/core/panic.h | 15 + lib/decoding/osmocom/core/utils.h | 129 +++++ 26 files changed, 4656 insertions(+) create mode 100644 lib/decoding/osmocom/core/CMakeLists.txt create mode 100644 lib/decoding/osmocom/core/bit16gen.h create mode 100644 lib/decoding/osmocom/core/bit32gen.h create mode 100644 lib/decoding/osmocom/core/bit64gen.h create mode 100644 lib/decoding/osmocom/core/bits.c create mode 100644 lib/decoding/osmocom/core/bits.h create mode 100644 lib/decoding/osmocom/core/bitvec.c create mode 100644 lib/decoding/osmocom/core/bitvec.h create mode 100644 lib/decoding/osmocom/core/conv.c create mode 100644 lib/decoding/osmocom/core/conv.h create mode 100644 lib/decoding/osmocom/core/conv_acc.c create mode 100644 lib/decoding/osmocom/core/conv_acc_generic.c create mode 100644 lib/decoding/osmocom/core/crc16gen.c create mode 100644 lib/decoding/osmocom/core/crc16gen.h create mode 100644 lib/decoding/osmocom/core/crc32gen.h create mode 100644 lib/decoding/osmocom/core/crc64gen.c create mode 100644 lib/decoding/osmocom/core/crc64gen.h create mode 100644 lib/decoding/osmocom/core/crc8gen.c create mode 100644 lib/decoding/osmocom/core/crc8gen.h create mode 100644 lib/decoding/osmocom/core/crcgen.h create mode 100644 lib/decoding/osmocom/core/defs.h create mode 100644 lib/decoding/osmocom/core/endian.h create mode 100644 lib/decoding/osmocom/core/linuxlist.h create mode 100644 lib/decoding/osmocom/core/panic.c create mode 100644 lib/decoding/osmocom/core/panic.h create mode 100644 lib/decoding/osmocom/core/utils.h (limited to 'lib/decoding/osmocom/core') diff --git a/lib/decoding/osmocom/core/CMakeLists.txt b/lib/decoding/osmocom/core/CMakeLists.txt new file mode 100644 index 0000000..ce8e60f --- /dev/null +++ b/lib/decoding/osmocom/core/CMakeLists.txt @@ -0,0 +1,11 @@ +add_sources( +bits.c +bitvec.c +conv_acc.c +conv_acc_generic.c +conv.c +crc16gen.c +crc64gen.c +crc8gen.c +panic.c +) diff --git a/lib/decoding/osmocom/core/bit16gen.h b/lib/decoding/osmocom/core/bit16gen.h new file mode 100644 index 0000000..5c6162c --- /dev/null +++ b/lib/decoding/osmocom/core/bit16gen.h @@ -0,0 +1,105 @@ +/* + * bit16gen.h + * + * Copyright (C) 2014 Max + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#pragma once + +/*! \brief load unaligned n-byte integer (little-endian encoding) into uint16_t + * \param[in] p Buffer where integer is stored + * \param[in] n Number of bytes stored in p + * \returns 16 bit unsigned integer + */ +static inline uint16_t osmo_load16le_ext(const void *p, uint8_t n) +{ + uint8_t i; + uint16_t r = 0; + const uint8_t *q = (uint8_t *)p; + for(i = 0; i < n; r |= ((uint16_t)q[i] << (8 * i)), i++); + return r; +} + +/*! \brief load unaligned n-byte integer (big-endian encoding) into uint16_t + * \param[in] p Buffer where integer is stored + * \param[in] n Number of bytes stored in p + * \returns 16 bit unsigned integer + */ +static inline uint16_t osmo_load16be_ext(const void *p, uint8_t n) +{ + uint8_t i; + uint16_t r = 0; + const uint8_t *q = (uint8_t *)p; + for(i = 0; i < n; r |= ((uint16_t)q[i] << (16 - 8* (1 + i))), i++); + return r; +} + + +/*! \brief store unaligned n-byte integer (little-endian encoding) from uint16_t + * \param[in] x unsigned 16 bit integer + * \param[out] p Buffer to store integer + * \param[in] n Number of bytes to store + */ +static inline void osmo_store16le_ext(uint16_t x, void *p, uint8_t n) +{ + uint8_t i; + uint8_t *q = (uint8_t *)p; + for(i = 0; i < n; q[i] = (x >> i * 8) & 0xFF, i++); +} + +/*! \brief store unaligned n-byte integer (big-endian encoding) from uint16_t + * \param[in] x unsigned 16 bit integer + * \param[out] p Buffer to store integer + * \param[in] n Number of bytes to store + */ +static inline void osmo_store16be_ext(uint16_t x, void *p, uint8_t n) +{ + uint8_t i; + uint8_t *q = (uint8_t *)p; + for(i = 0; i < n; q[i] = (x >> ((n - 1 - i) * 8)) & 0xFF, i++); +} + + +/* Convenience function for most-used cases */ + + +/*! \brief load unaligned 16-bit integer (little-endian encoding) */ +static inline uint16_t osmo_load16le(const void *p) +{ + return osmo_load16le_ext(p, 16 / 8); +} + +/*! \brief load unaligned 16-bit integer (big-endian encoding) */ +static inline uint16_t osmo_load16be(const void *p) +{ + return osmo_load16be_ext(p, 16 / 8); +} + + +/*! \brief store unaligned 16-bit integer (little-endian encoding) */ +static inline void osmo_store16le(uint16_t x, void *p) +{ + osmo_store16le_ext(x, p, 16 / 8); +} + +/*! \brief store unaligned 16-bit integer (big-endian encoding) */ +static inline void osmo_store16be(uint16_t x, void *p) +{ + osmo_store16be_ext(x, p, 16 / 8); +} diff --git a/lib/decoding/osmocom/core/bit32gen.h b/lib/decoding/osmocom/core/bit32gen.h new file mode 100644 index 0000000..6640e76 --- /dev/null +++ b/lib/decoding/osmocom/core/bit32gen.h @@ -0,0 +1,105 @@ +/* + * bit32gen.h + * + * Copyright (C) 2014 Max + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#pragma once + +/*! \brief load unaligned n-byte integer (little-endian encoding) into uint32_t + * \param[in] p Buffer where integer is stored + * \param[in] n Number of bytes stored in p + * \returns 32 bit unsigned integer + */ +static inline uint32_t osmo_load32le_ext(const void *p, uint8_t n) +{ + uint8_t i; + uint32_t r = 0; + const uint8_t *q = (uint8_t *)p; + for(i = 0; i < n; r |= ((uint32_t)q[i] << (8 * i)), i++); + return r; +} + +/*! \brief load unaligned n-byte integer (big-endian encoding) into uint32_t + * \param[in] p Buffer where integer is stored + * \param[in] n Number of bytes stored in p + * \returns 32 bit unsigned integer + */ +static inline uint32_t osmo_load32be_ext(const void *p, uint8_t n) +{ + uint8_t i; + uint32_t r = 0; + const uint8_t *q = (uint8_t *)p; + for(i = 0; i < n; r |= ((uint32_t)q[i] << (32 - 8* (1 + i))), i++); + return r; +} + + +/*! \brief store unaligned n-byte integer (little-endian encoding) from uint32_t + * \param[in] x unsigned 32 bit integer + * \param[out] p Buffer to store integer + * \param[in] n Number of bytes to store + */ +static inline void osmo_store32le_ext(uint32_t x, void *p, uint8_t n) +{ + uint8_t i; + uint8_t *q = (uint8_t *)p; + for(i = 0; i < n; q[i] = (x >> i * 8) & 0xFF, i++); +} + +/*! \brief store unaligned n-byte integer (big-endian encoding) from uint32_t + * \param[in] x unsigned 32 bit integer + * \param[out] p Buffer to store integer + * \param[in] n Number of bytes to store + */ +static inline void osmo_store32be_ext(uint32_t x, void *p, uint8_t n) +{ + uint8_t i; + uint8_t *q = (uint8_t *)p; + for(i = 0; i < n; q[i] = (x >> ((n - 1 - i) * 8)) & 0xFF, i++); +} + + +/* Convenience function for most-used cases */ + + +/*! \brief load unaligned 32-bit integer (little-endian encoding) */ +static inline uint32_t osmo_load32le(const void *p) +{ + return osmo_load32le_ext(p, 32 / 8); +} + +/*! \brief load unaligned 32-bit integer (big-endian encoding) */ +static inline uint32_t osmo_load32be(const void *p) +{ + return osmo_load32be_ext(p, 32 / 8); +} + + +/*! \brief store unaligned 32-bit integer (little-endian encoding) */ +static inline void osmo_store32le(uint32_t x, void *p) +{ + osmo_store32le_ext(x, p, 32 / 8); +} + +/*! \brief store unaligned 32-bit integer (big-endian encoding) */ +static inline void osmo_store32be(uint32_t x, void *p) +{ + osmo_store32be_ext(x, p, 32 / 8); +} diff --git a/lib/decoding/osmocom/core/bit64gen.h b/lib/decoding/osmocom/core/bit64gen.h new file mode 100644 index 0000000..8c7b709 --- /dev/null +++ b/lib/decoding/osmocom/core/bit64gen.h @@ -0,0 +1,105 @@ +/* + * bit64gen.h + * + * Copyright (C) 2014 Max + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#pragma once + +/*! \brief load unaligned n-byte integer (little-endian encoding) into uint64_t + * \param[in] p Buffer where integer is stored + * \param[in] n Number of bytes stored in p + * \returns 64 bit unsigned integer + */ +static inline uint64_t osmo_load64le_ext(const void *p, uint8_t n) +{ + uint8_t i; + uint64_t r = 0; + const uint8_t *q = (uint8_t *)p; + for(i = 0; i < n; r |= ((uint64_t)q[i] << (8 * i)), i++); + return r; +} + +/*! \brief load unaligned n-byte integer (big-endian encoding) into uint64_t + * \param[in] p Buffer where integer is stored + * \param[in] n Number of bytes stored in p + * \returns 64 bit unsigned integer + */ +static inline uint64_t osmo_load64be_ext(const void *p, uint8_t n) +{ + uint8_t i; + uint64_t r = 0; + const uint8_t *q = (uint8_t *)p; + for(i = 0; i < n; r |= ((uint64_t)q[i] << (64 - 8* (1 + i))), i++); + return r; +} + + +/*! \brief store unaligned n-byte integer (little-endian encoding) from uint64_t + * \param[in] x unsigned 64 bit integer + * \param[out] p Buffer to store integer + * \param[in] n Number of bytes to store + */ +static inline void osmo_store64le_ext(uint64_t x, void *p, uint8_t n) +{ + uint8_t i; + uint8_t *q = (uint8_t *)p; + for(i = 0; i < n; q[i] = (x >> i * 8) & 0xFF, i++); +} + +/*! \brief store unaligned n-byte integer (big-endian encoding) from uint64_t + * \param[in] x unsigned 64 bit integer + * \param[out] p Buffer to store integer + * \param[in] n Number of bytes to store + */ +static inline void osmo_store64be_ext(uint64_t x, void *p, uint8_t n) +{ + uint8_t i; + uint8_t *q = (uint8_t *)p; + for(i = 0; i < n; q[i] = (x >> ((n - 1 - i) * 8)) & 0xFF, i++); +} + + +/* Convenience function for most-used cases */ + + +/*! \brief load unaligned 64-bit integer (little-endian encoding) */ +static inline uint64_t osmo_load64le(const void *p) +{ + return osmo_load64le_ext(p, 64 / 8); +} + +/*! \brief load unaligned 64-bit integer (big-endian encoding) */ +static inline uint64_t osmo_load64be(const void *p) +{ + return osmo_load64be_ext(p, 64 / 8); +} + + +/*! \brief store unaligned 64-bit integer (little-endian encoding) */ +static inline void osmo_store64le(uint64_t x, void *p) +{ + osmo_store64le_ext(x, p, 64 / 8); +} + +/*! \brief store unaligned 64-bit integer (big-endian encoding) */ +static inline void osmo_store64be(uint64_t x, void *p) +{ + osmo_store64be_ext(x, p, 64 / 8); +} diff --git a/lib/decoding/osmocom/core/bits.c b/lib/decoding/osmocom/core/bits.c new file mode 100644 index 0000000..8837c1f --- /dev/null +++ b/lib/decoding/osmocom/core/bits.c @@ -0,0 +1,311 @@ +/* + * (C) 2011 by Harald Welte + * (C) 2011 by Sylvain Munaut + * + * All Rights Reserved + * + * SPDX-License-Identifier: GPL-2.0+ + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * + */ + +#include + +#include + +/*! \addtogroup bits + * @{ + * Osmocom bit level support code. + * + * This module implements the notion of different bit-fields, such as + * - unpacked bits (\ref ubit_t), i.e. 1 bit per byte + * - packed bits (\ref pbit_t), i.e. 8 bits per byte + * - soft bits (\ref sbit_t), 1 bit per byte from -127 to 127 + * + * \file bits.c */ + +/*! convert unpacked bits to packed bits, return length in bytes + * \param[out] out output buffer of packed bits + * \param[in] in input buffer of unpacked bits + * \param[in] num_bits number of bits + */ +int osmo_ubit2pbit(pbit_t *out, const ubit_t *in, unsigned int num_bits) +{ + unsigned int i; + uint8_t curbyte = 0; + pbit_t *outptr = out; + + for (i = 0; i < num_bits; i++) { + uint8_t bitnum = 7 - (i % 8); + + curbyte |= (in[i] << bitnum); + + if(i % 8 == 7){ + *outptr++ = curbyte; + curbyte = 0; + } + } + /* we have a non-modulo-8 bitcount */ + if (i % 8) + *outptr++ = curbyte; + + return outptr - out; +} + +/*! Shift unaligned input to octet-aligned output + * \param[out] out output buffer, unaligned + * \param[in] in input buffer, octet-aligned + * \param[in] num_nibbles number of nibbles + */ +void osmo_nibble_shift_right(uint8_t *out, const uint8_t *in, + unsigned int num_nibbles) +{ + unsigned int i, num_whole_bytes = num_nibbles / 2; + if (!num_whole_bytes) + return; + + /* first byte: upper nibble empty, lower nibble from src */ + out[0] = (in[0] >> 4); + + /* bytes 1.. */ + for (i = 1; i < num_whole_bytes; i++) + out[i] = ((in[i - 1] & 0xF) << 4) | (in[i] >> 4); + + /* shift the last nibble, in case there's an odd count */ + i = num_whole_bytes; + if (num_nibbles & 1) + out[i] = ((in[i - 1] & 0xF) << 4) | (in[i] >> 4); + else + out[i] = (in[i - 1] & 0xF) << 4; +} + +/*! Shift unaligned input to octet-aligned output + * \param[out] out output buffer, octet-aligned + * \param[in] in input buffer, unaligned + * \param[in] num_nibbles number of nibbles + */ +void osmo_nibble_shift_left_unal(uint8_t *out, const uint8_t *in, + unsigned int num_nibbles) +{ + unsigned int i, num_whole_bytes = num_nibbles / 2; + if (!num_whole_bytes) + return; + + for (i = 0; i < num_whole_bytes; i++) + out[i] = ((in[i] & 0xF) << 4) | (in[i + 1] >> 4); + + /* shift the last nibble, in case there's an odd count */ + i = num_whole_bytes; + if (num_nibbles & 1) + out[i] = (in[i] & 0xF) << 4; +} + +/*! convert unpacked bits to soft bits + * \param[out] out output buffer of soft bits + * \param[in] in input buffer of unpacked bits + * \param[in] num_bits number of bits + */ +void osmo_ubit2sbit(sbit_t *out, const ubit_t *in, unsigned int num_bits) +{ + unsigned int i; + for (i = 0; i < num_bits; i++) + out[i] = in[i] ? -127 : 127; +} + +/*! convert soft bits to unpacked bits + * \param[out] out output buffer of unpacked bits + * \param[in] in input buffer of soft bits + * \param[in] num_bits number of bits + */ +void osmo_sbit2ubit(ubit_t *out, const sbit_t *in, unsigned int num_bits) +{ + unsigned int i; + for (i = 0; i < num_bits; i++) + out[i] = in[i] < 0; +} + +/*! convert packed bits to unpacked bits, return length in bytes + * \param[out] out output buffer of unpacked bits + * \param[in] in input buffer of packed bits + * \param[in] num_bits number of bits + * \return number of bytes used in \ref out + */ +int osmo_pbit2ubit(ubit_t *out, const pbit_t *in, unsigned int num_bits) +{ + unsigned int i; + ubit_t *cur = out; + ubit_t *limit = out + num_bits; + + for (i = 0; i < (num_bits/8)+1; i++) { + pbit_t byte = in[i]; + *cur++ = (byte >> 7) & 1; + if (cur >= limit) + break; + *cur++ = (byte >> 6) & 1; + if (cur >= limit) + break; + *cur++ = (byte >> 5) & 1; + if (cur >= limit) + break; + *cur++ = (byte >> 4) & 1; + if (cur >= limit) + break; + *cur++ = (byte >> 3) & 1; + if (cur >= limit) + break; + *cur++ = (byte >> 2) & 1; + if (cur >= limit) + break; + *cur++ = (byte >> 1) & 1; + if (cur >= limit) + break; + *cur++ = (byte >> 0) & 1; + if (cur >= limit) + break; + } + return cur - out; +} + +/*! convert unpacked bits to packed bits (extended options) + * \param[out] out output buffer of packed bits + * \param[in] out_ofs offset into output buffer + * \param[in] in input buffer of unpacked bits + * \param[in] in_ofs offset into input buffer + * \param[in] num_bits number of bits + * \param[in] lsb_mode Encode bits in LSB orde instead of MSB + * \returns length in bytes (max written offset of output buffer + 1) + */ +int osmo_ubit2pbit_ext(pbit_t *out, unsigned int out_ofs, + const ubit_t *in, unsigned int in_ofs, + unsigned int num_bits, int lsb_mode) +{ + int i, op, bn; + for (i=0; i>3] |= 1 << bn; + else + out[op>>3] &= ~(1 << bn); + } + return ((out_ofs + num_bits - 1) >> 3) + 1; +} + +/*! convert packed bits to unpacked bits (extended options) + * \param[out] out output buffer of unpacked bits + * \param[in] out_ofs offset into output buffer + * \param[in] in input buffer of packed bits + * \param[in] in_ofs offset into input buffer + * \param[in] num_bits number of bits + * \param[in] lsb_mode Encode bits in LSB orde instead of MSB + * \returns length in bytes (max written offset of output buffer + 1) + */ +int osmo_pbit2ubit_ext(ubit_t *out, unsigned int out_ofs, + const pbit_t *in, unsigned int in_ofs, + unsigned int num_bits, int lsb_mode) +{ + int i, ip, bn; + for (i=0; i>3] & (1<> 1; + if (k & 2) x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2; + if (k & 4) x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4; + if (k & 8) x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >> 8; + if (k & 16) x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16; + + return x; +} + +/*! reverse the bit-order in each byte of a dword + * \param[in] x 32bit input value + * \returns 32bit value where bits of each byte have been reversed + * + * See Chapter 7 "Hackers Delight" + */ +uint32_t osmo_revbytebits_32(uint32_t x) +{ + x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1; + x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2; + x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4; + + return x; +} + +/*! reverse the bit order in a byte + * \param[in] x 8bit input value + * \returns 8bit value where bits order has been reversed + * + * See Chapter 7 "Hackers Delight" + */ +uint32_t osmo_revbytebits_8(uint8_t x) +{ + x = (x & 0x55) << 1 | (x & 0xAA) >> 1; + x = (x & 0x33) << 2 | (x & 0xCC) >> 2; + x = (x & 0x0F) << 4 | (x & 0xF0) >> 4; + + return x; +} + +/*! reverse bit-order of each byte in a buffer + * \param[in] buf buffer containing bytes to be bit-reversed + * \param[in] len length of buffer in bytes + * + * This function reverses the bits in each byte of the buffer + */ +void osmo_revbytebits_buf(uint8_t *buf, int len) +{ + unsigned int i; + unsigned int unaligned_cnt; + int len_remain = len; + + unaligned_cnt = ((unsigned long)buf & 3); + for (i = 0; i < unaligned_cnt; i++) { + buf[i] = osmo_revbytebits_8(buf[i]); + len_remain--; + if (len_remain <= 0) + return; + } + + for (i = unaligned_cnt; i + 3 < len; i += 4) { + osmo_store32be(osmo_revbytebits_32(osmo_load32be(buf + i)), buf + i); + len_remain -= 4; + } + + for (i = len - len_remain; i < len; i++) { + buf[i] = osmo_revbytebits_8(buf[i]); + len_remain--; + } +} + +/*! @} */ diff --git a/lib/decoding/osmocom/core/bits.h b/lib/decoding/osmocom/core/bits.h new file mode 100644 index 0000000..b1b8040 --- /dev/null +++ b/lib/decoding/osmocom/core/bits.h @@ -0,0 +1,122 @@ +/*! \file bits.h + * Osmocom bit level support code. + * + */ + +#pragma once + +#include +#include + +#include +#include +#include + +/*! \defgroup bits soft, unpacked and packed bits + * @{ + * \file bits.h */ + +/*! soft bit with value (-127...127), as commonly used in + * communications receivers such as [viterbi] decoders */ +typedef int8_t sbit_t; + +/*! unpacked bit (0 or 1): 1 bit per byte */ +typedef uint8_t ubit_t; + +/*! packed bits (8 bits in a byte). + * NOTE on the endian-ness of \ref pbit_t: + * - Bits in a \ref pbit_t are ordered MSB first, i.e. 0x80 is the first bit. + * - Bit i in a \ref pbit_t array is array[i/8] & (1<<(7-i%8)) */ +typedef uint8_t pbit_t; + +/*! determine how many bytes we would need for \a num_bits packed bits + * \param[in] num_bits Number of packed bits + * \returns number of bytes needed for \a num_bits packed bits + */ +static inline unsigned int osmo_pbit_bytesize(unsigned int num_bits) +{ + unsigned int pbit_bytesize = num_bits / 8; + + if (num_bits % 8) + pbit_bytesize++; + + return pbit_bytesize; +} + +int osmo_ubit2pbit(pbit_t *out, const ubit_t *in, unsigned int num_bits); + +int osmo_pbit2ubit(ubit_t *out, const pbit_t *in, unsigned int num_bits); + +void osmo_nibble_shift_right(uint8_t *out, const uint8_t *in, + unsigned int num_nibbles); +void osmo_nibble_shift_left_unal(uint8_t *out, const uint8_t *in, + unsigned int num_nibbles); + +void osmo_ubit2sbit(sbit_t *out, const ubit_t *in, unsigned int num_bits); +void osmo_sbit2ubit(ubit_t *out, const sbit_t *in, unsigned int num_bits); + +int osmo_ubit2pbit_ext(pbit_t *out, unsigned int out_ofs, + const ubit_t *in, unsigned int in_ofs, + unsigned int num_bits, int lsb_mode); + +int osmo_pbit2ubit_ext(ubit_t *out, unsigned int out_ofs, + const pbit_t *in, unsigned int in_ofs, + unsigned int num_bits, int lsb_mode); + +#define OSMO_BIN_SPEC "%d%d%d%d%d%d%d%d" +#define OSMO_BIN_PRINT(byte) \ + (byte & 0x80 ? 1 : 0), \ + (byte & 0x40 ? 1 : 0), \ + (byte & 0x20 ? 1 : 0), \ + (byte & 0x10 ? 1 : 0), \ + (byte & 0x08 ? 1 : 0), \ + (byte & 0x04 ? 1 : 0), \ + (byte & 0x02 ? 1 : 0), \ + (byte & 0x01 ? 1 : 0) + +#define OSMO_BIT_SPEC "%c%c%c%c%c%c%c%c" +#define OSMO_BIT_PRINT_EX(byte, ch) \ + (byte & 0x80 ? ch : '.'), \ + (byte & 0x40 ? ch : '.'), \ + (byte & 0x20 ? ch : '.'), \ + (byte & 0x10 ? ch : '.'), \ + (byte & 0x08 ? ch : '.'), \ + (byte & 0x04 ? ch : '.'), \ + (byte & 0x02 ? ch : '.'), \ + (byte & 0x01 ? ch : '.') + +#define OSMO_BIT_PRINT(byte) OSMO_BIT_PRINT_EX(byte, '1') + +/* BIT REVERSAL */ + +/*! bit-reversal mode for osmo_bit_reversal() */ +enum osmo_br_mode { + /*! reverse all bits in a 32bit dword */ + OSMO_BR_BITS_IN_DWORD = 31, + /*! reverse byte order in a 32bit dword */ + OSMO_BR_BYTES_IN_DWORD = 24, + /*! reverse bits of each byte in a 32bit dword */ + OSMO_BR_BITS_IN_BYTE = 7, + /*! swap the two 16bit words in a 32bit dword */ + OSMO_BR_WORD_SWAP = 16, +}; + +uint32_t osmo_bit_reversal(uint32_t x, enum osmo_br_mode k); + +uint32_t osmo_revbytebits_32(uint32_t x); + +uint32_t osmo_revbytebits_8(uint8_t x); + +void osmo_revbytebits_buf(uint8_t *buf, int len); + +/*! left circular shift + * \param[in] in The 16 bit unsigned integer to be rotated + * \param[in] shift Number of bits to shift \a in to, [0;16] bits + * \returns shifted value + */ +static inline uint16_t osmo_rol16(uint16_t in, unsigned shift) +{ + return (in << shift) | (in >> (16 - shift)); +} + +/*! @} */ diff --git a/lib/decoding/osmocom/core/bitvec.c b/lib/decoding/osmocom/core/bitvec.c new file mode 100644 index 0000000..414c719 --- /dev/null +++ b/lib/decoding/osmocom/core/bitvec.c @@ -0,0 +1,708 @@ +/* (C) 2009 by Harald Welte + * (C) 2012 Ivan Klyuchnikov + * (C) 2015 by sysmocom - s.f.m.c. GmbH + * + * All Rights Reserved + * + * SPDX-License-Identifier: GPL-2.0+ + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * + */ + +/*! \addtogroup bitvec + * @{ + * Osmocom bit vector abstraction utility routines. + * + * These functions assume a MSB (most significant bit) first layout of the + * bits, so that for instance the 5 bit number abcde (a is MSB) can be + * embedded into a byte sequence like in xxxxxxab cdexxxxx. The bit count + * starts with the MSB, so the bits in a byte are numbered (MSB) 01234567 (LSB). + * Note that there are other incompatible encodings, like it is used + * for the EGPRS RLC data block headers (there the bits are numbered from LSB + * to MSB). + * + * \file bitvec.c */ + +#include +#include +#include +#include +#include + +#include +#include + +#define BITNUM_FROM_COMP(byte, bit) ((byte*8)+bit) + +static inline unsigned int bytenum_from_bitnum(unsigned int bitnum) +{ + unsigned int bytenum = bitnum / 8; + + return bytenum; +} + +/* convert ZERO/ONE/L/H to a bitmask at given pos in a byte */ +static uint8_t bitval2mask(enum bit_value bit, uint8_t bitnum) +{ + int bitval; + + switch (bit) { + case ZERO: + bitval = (0 << bitnum); + break; + case ONE: + bitval = (1 << bitnum); + break; + case L: + bitval = ((0x2b ^ (0 << bitnum)) & (1 << bitnum)); + break; + case H: + bitval = ((0x2b ^ (1 << bitnum)) & (1 << bitnum)); + break; + default: + return 0; + } + return bitval; +} + +/*! check if the bit is 0 or 1 for a given position inside a bitvec + * \param[in] bv the bit vector on which to check + * \param[in] bitnr the bit number inside the bit vector to check + * \return value of the requested bit + */ +enum bit_value bitvec_get_bit_pos(const struct bitvec *bv, unsigned int bitnr) +{ + unsigned int bytenum = bytenum_from_bitnum(bitnr); + unsigned int bitnum = 7 - (bitnr % 8); + uint8_t bitval; + + if (bytenum >= bv->data_len) + return -EINVAL; + + bitval = bitval2mask(ONE, bitnum); + + if (bv->data[bytenum] & bitval) + return ONE; + + return ZERO; +} + +/*! check if the bit is L or H for a given position inside a bitvec + * \param[in] bv the bit vector on which to check + * \param[in] bitnr the bit number inside the bit vector to check + * \return value of the requested bit + */ +enum bit_value bitvec_get_bit_pos_high(const struct bitvec *bv, + unsigned int bitnr) +{ + unsigned int bytenum = bytenum_from_bitnum(bitnr); + unsigned int bitnum = 7 - (bitnr % 8); + uint8_t bitval; + + if (bytenum >= bv->data_len) + return -EINVAL; + + bitval = bitval2mask(H, bitnum); + + if ((bv->data[bytenum] & (1 << bitnum)) == bitval) + return H; + + return L; +} + +/*! get the Nth set bit inside the bit vector + * \param[in] bv the bit vector to use + * \param[in] n the bit number to get + * \returns the bit number (offset) of the Nth set bit in \a bv + */ +unsigned int bitvec_get_nth_set_bit(const struct bitvec *bv, unsigned int n) +{ + unsigned int i, k = 0; + + for (i = 0; i < bv->data_len*8; i++) { + if (bitvec_get_bit_pos(bv, i) == ONE) { + k++; + if (k == n) + return i; + } + } + + return 0; +} + +/*! set a bit at given position in a bit vector + * \param[in] bv bit vector on which to operate + * \param[in] bitnr number of bit to be set + * \param[in] bit value to which the bit is to be set + * \returns 0 on success, negative value on error + */ +inline int bitvec_set_bit_pos(struct bitvec *bv, unsigned int bitnr, + enum bit_value bit) +{ + unsigned int bytenum = bytenum_from_bitnum(bitnr); + unsigned int bitnum = 7 - (bitnr % 8); + uint8_t bitval; + + if (bytenum >= bv->data_len) + return -EINVAL; + + /* first clear the bit */ + bitval = bitval2mask(ONE, bitnum); + bv->data[bytenum] &= ~bitval; + + /* then set it to desired value */ + bitval = bitval2mask(bit, bitnum); + bv->data[bytenum] |= bitval; + + return 0; +} + +/*! set the next bit inside a bitvec + * \param[in] bv bit vector to be used + * \param[in] bit value of the bit to be set + * \returns 0 on success, negative value on error + */ +inline int bitvec_set_bit(struct bitvec *bv, enum bit_value bit) +{ + int rc; + + rc = bitvec_set_bit_pos(bv, bv->cur_bit, bit); + if (!rc) + bv->cur_bit++; + + return rc; +} + +/*! get the next bit (low/high) inside a bitvec + * \return value of th next bit in the vector */ +int bitvec_get_bit_high(struct bitvec *bv) +{ + int rc; + + rc = bitvec_get_bit_pos_high(bv, bv->cur_bit); + if (rc >= 0) + bv->cur_bit++; + + return rc; +} + +/*! set multiple bits (based on array of bitvals) at current pos + * \param[in] bv bit vector + * \param[in] bits array of \ref bit_value + * \param[in] count number of bits to set + * \return 0 on success; negative in case of error */ +int bitvec_set_bits(struct bitvec *bv, const enum bit_value *bits, unsigned int count) +{ + int i, rc; + + for (i = 0; i < count; i++) { + rc = bitvec_set_bit(bv, bits[i]); + if (rc) + return rc; + } + + return 0; +} + +/*! set multiple bits (based on numeric value) at current pos. + * \param[in] bv bit vector. + * \param[in] v mask representing which bits needs to be set. + * \param[in] num_bits number of meaningful bits in the mask. + * \param[in] use_lh whether to interpret the bits as L/H values or as 0/1. + * \return 0 on success; negative in case of error. */ +int bitvec_set_u64(struct bitvec *bv, uint64_t v, uint8_t num_bits, bool use_lh) +{ + uint8_t i; + + if (num_bits > 64) + return -E2BIG; + + for (i = 0; i < num_bits; i++) { + int rc; + enum bit_value bit = use_lh ? L : 0; + + if (v & ((uint64_t)1 << (num_bits - i - 1))) + bit = use_lh ? H : 1; + + rc = bitvec_set_bit(bv, bit); + if (rc != 0) + return rc; + } + + return 0; +} + +/*! set multiple bits (based on numeric value) at current pos. + * \return 0 in case of success; negative in case of error. */ +int bitvec_set_uint(struct bitvec *bv, unsigned int ui, unsigned int num_bits) +{ + return bitvec_set_u64(bv, ui, num_bits, false); +} + +/*! get multiple bits (num_bits) from beginning of vector (MSB side) + * \return 16bit signed integer retrieved from bit vector */ +int16_t bitvec_get_int16_msb(const struct bitvec *bv, unsigned int num_bits) +{ + if (num_bits > 15 || bv->cur_bit < num_bits) + return -EINVAL; + + if (num_bits < 9) + return bv->data[0] >> (8 - num_bits); + + return osmo_load16be(bv->data) >> (16 - num_bits); +} + +/*! get multiple bits (based on numeric value) from current pos + * \return integer value retrieved from bit vector */ +int bitvec_get_uint(struct bitvec *bv, unsigned int num_bits) +{ + int i; + unsigned int ui = 0; + + for (i = 0; i < num_bits; i++) { + int bit = bitvec_get_bit_pos(bv, bv->cur_bit); + if (bit < 0) + return bit; + if (bit) + ui |= (1 << (num_bits - i - 1)); + bv->cur_bit++; + } + + return ui; +} + +/*! fill num_bits with \fill starting from the current position + * \return 0 on success; negative otherwise (out of vector boundary) + */ +int bitvec_fill(struct bitvec *bv, unsigned int num_bits, enum bit_value fill) +{ + unsigned i, stop = bv->cur_bit + num_bits; + for (i = bv->cur_bit; i < stop; i++) + if (bitvec_set_bit(bv, fill) < 0) + return -EINVAL; + + return 0; +} + +/*! pad all remaining bits up to num_bits + * \return 0 on success; negative otherwise */ +int bitvec_spare_padding(struct bitvec *bv, unsigned int up_to_bit) +{ + int n = up_to_bit - bv->cur_bit + 1; + if (n < 1) + return 0; + + return bitvec_fill(bv, n, L); +} + +/*! find first bit set in bit vector + * \return 0 on success; negative otherwise */ +int bitvec_find_bit_pos(const struct bitvec *bv, unsigned int n, + enum bit_value val) +{ + unsigned int i; + + for (i = n; i < bv->data_len*8; i++) { + if (bitvec_get_bit_pos(bv, i) == val) + return i; + } + + return -1; +} + +/*! get multiple bytes from current pos + * Assumes MSB first encoding. + * \param[in] bv bit vector + * \param[in] bytes array + * \param[in] count number of bytes to copy + * \return 0 on success; negative otherwise + */ +int bitvec_get_bytes(struct bitvec *bv, uint8_t *bytes, unsigned int count) +{ + int byte_offs = bytenum_from_bitnum(bv->cur_bit); + int bit_offs = bv->cur_bit % 8; + uint8_t c, last_c; + int i; + uint8_t *src; + + if (byte_offs + count + (bit_offs ? 1 : 0) > bv->data_len) + return -EINVAL; + + if (bit_offs == 0) { + memcpy(bytes, bv->data + byte_offs, count); + } else { + src = bv->data + byte_offs; + last_c = *(src++); + for (i = count; i > 0; i--) { + c = *(src++); + *(bytes++) = + (last_c << bit_offs) | + (c >> (8 - bit_offs)); + last_c = c; + } + } + + bv->cur_bit += count * 8; + return 0; +} + +/*! set multiple bytes at current pos + * Assumes MSB first encoding. + * \param[in] bv bit vector + * \param[in] bytes array + * \param[in] count number of bytes to copy + * \return 0 on success; negative otherwise + */ +int bitvec_set_bytes(struct bitvec *bv, const uint8_t *bytes, unsigned int count) +{ + int byte_offs = bytenum_from_bitnum(bv->cur_bit); + int bit_offs = bv->cur_bit % 8; + uint8_t c, last_c; + int i; + uint8_t *dst; + + if (byte_offs + count + (bit_offs ? 1 : 0) > bv->data_len) + return -EINVAL; + + if (bit_offs == 0) { + memcpy(bv->data + byte_offs, bytes, count); + } else if (count > 0) { + dst = bv->data + byte_offs; + /* Get lower bits of first dst byte */ + last_c = *dst >> (8 - bit_offs); + for (i = count; i > 0; i--) { + c = *(bytes++); + *(dst++) = + (last_c << (8 - bit_offs)) | + (c >> bit_offs); + last_c = c; + } + /* Overwrite lower bits of N+1 dst byte */ + *dst = (*dst & ((1 << (8 - bit_offs)) - 1)) | + (last_c << (8 - bit_offs)); + } + + bv->cur_bit += count * 8; + return 0; +} + +/*! Allocate a bit vector + * \param[in] size Number of bits in the vector + * \param[in] ctx Context from which to allocate + * \return pointer to allocated vector; NULL in case of error / +struct bitvec *bitvec_alloc(unsigned int size, TALLOC_CTX *ctx) +{ + struct bitvec *bv = talloc_zero(ctx, struct bitvec); + if (!bv) + return NULL; + + bv->data = talloc_zero_array(bv, uint8_t, size); + if (!(bv->data)) { + talloc_free(bv); + return NULL; + } + + bv->data_len = size; + bv->cur_bit = 0; + return bv; +} + +/*! Free a bit vector (release its memory) + * \param[in] bit vector to free * +void bitvec_free(struct bitvec *bv) +{ + talloc_free(bv->data); + talloc_free(bv); +} +*/ +/*! Export a bit vector to a buffer + * \param[in] bitvec (unpacked bits) + * \param[out] buffer for the unpacked bits + * \return number of bytes (= bits) copied */ +unsigned int bitvec_pack(const struct bitvec *bv, uint8_t *buffer) +{ + unsigned int i = 0; + for (i = 0; i < bv->data_len; i++) + buffer[i] = bv->data[i]; + + return i; +} + +/*! Copy buffer of unpacked bits into bit vector + * \param[in] buffer unpacked input bits + * \param[out] bv unpacked bit vector + * \return number of bytes (= bits) copied */ +unsigned int bitvec_unpack(struct bitvec *bv, const uint8_t *buffer) +{ + unsigned int i = 0; + for (i = 0; i < bv->data_len; i++) + bv->data[i] = buffer[i]; + + return i; +} + +/*! read hexadecimap string into a bit vector + * \param[in] src string containing hex digits + * \param[out] bv unpacked bit vector + * \return 0 in case of success; 1 in case of error + */ +int bitvec_unhex(struct bitvec *bv, const char *src) +{ + unsigned i; + unsigned val; + unsigned write_index = 0; + unsigned digits = bv->data_len * 2; + + for (i = 0; i < digits; i++) { + if (sscanf(src + i, "%1x", &val) < 1) { + return 1; + } + bitvec_write_field(bv, &write_index, val, 4); + } + return 0; +} + +/*! read part of the vector + * \param[in] bv The boolean vector to work on + * \param[in,out] read_index Where reading supposed to start in the vector + * \param[in] len How many bits to read from vector + * \returns read bits or negative value on error + */ +uint64_t bitvec_read_field(struct bitvec *bv, unsigned int *read_index, unsigned int len) +{ + unsigned int i; + uint64_t ui = 0; + bv->cur_bit = *read_index; + + for (i = 0; i < len; i++) { + int bit = bitvec_get_bit_pos((const struct bitvec *)bv, bv->cur_bit); + if (bit < 0) + return bit; + if (bit) + ui |= ((uint64_t)1 << (len - i - 1)); + bv->cur_bit++; + } + *read_index += len; + return ui; +} + +/*! write into the vector + * \param[in] bv The boolean vector to work on + * \param[in,out] write_index Where writing supposed to start in the vector + * \param[in] len How many bits to write + * \returns next write index or negative value on error + */ +int bitvec_write_field(struct bitvec *bv, unsigned int *write_index, uint64_t val, unsigned int len) +{ + int rc; + + bv->cur_bit = *write_index; + + rc = bitvec_set_u64(bv, val, len, false); + if (rc != 0) + return rc; + + *write_index += len; + + return 0; +} + +/*! convert enum to corresponding character + * \param v input value (bit) + * \return single character, either 0, 1, L or H */ +char bit_value_to_char(enum bit_value v) +{ + switch (v) { + case ZERO: return '0'; + case ONE: return '1'; + case L: return 'L'; + case H: return 'H'; + default: abort(); + } +} + +/*! prints bit vector to provided string + * It's caller's responsibility to ensure that we won't shoot him in the foot: + * the provided buffer should be at lest cur_bit + 1 bytes long + */ +void bitvec_to_string_r(const struct bitvec *bv, char *str) +{ + unsigned i, pos = 0; + char *cur = str; + for (i = 0; i < bv->cur_bit; i++) { + if (0 == i % 8) + *cur++ = ' '; + *cur++ = bit_value_to_char(bitvec_get_bit_pos(bv, i)); + pos++; + } + *cur = 0; +} + +/* we assume that x have at least 1 non-b bit */ +static inline unsigned leading_bits(uint8_t x, bool b) +{ + if (b) { + if (x < 0x80) return 0; + if (x < 0xC0) return 1; + if (x < 0xE0) return 2; + if (x < 0xF0) return 3; + if (x < 0xF8) return 4; + if (x < 0xFC) return 5; + if (x < 0xFE) return 6; + } else { + if (x > 0x7F) return 0; + if (x > 0x3F) return 1; + if (x > 0x1F) return 2; + if (x > 0xF) return 3; + if (x > 7) return 4; + if (x > 3) return 5; + if (x > 1) return 6; + } + return 7; +} +/*! force bit vector to all 0 and current bit to the beginnig of the vector */ +void bitvec_zero(struct bitvec *bv) +{ + bv->cur_bit = 0; + memset(bv->data, 0, bv->data_len); +} + +/*! Return number (bits) of uninterrupted bit run in vector starting from the MSB + * \param[in] bv The boolean vector to work on + * \param[in] b The boolean, sequence of which is looked at from the vector start + * \returns Number of consecutive bits of \p b in \p bv + */ +unsigned bitvec_rl(const struct bitvec *bv, bool b) +{ + unsigned i; + for (i = 0; i < (bv->cur_bit % 8 ? bv->cur_bit / 8 + 1 : bv->cur_bit / 8); i++) { + if ( (b ? 0xFF : 0) != bv->data[i]) + return i * 8 + leading_bits(bv->data[i], b); + } + + return bv->cur_bit; +} + +/*! Return number (bits) of uninterrupted bit run in vector + * starting from the current bit + * \param[in] bv The boolean vector to work on + * \param[in] b The boolean, sequence of 1's or 0's to be checked + * \param[in] max_bits Total Number of Uncmopresed bits + * \returns Number of consecutive bits of \p b in \p bv and cur_bit will + * \go to cur_bit + number of consecutive bit + */ +unsigned bitvec_rl_curbit(struct bitvec *bv, bool b, int max_bits) +{ + unsigned i = 0; + unsigned j = 8; + int temp_res = 0; + int count = 0; + unsigned readIndex = bv->cur_bit; + unsigned remaining_bits = max_bits % 8; + unsigned remaining_bytes = max_bits / 8; + unsigned byte_mask = 0xFF; + + if (readIndex % 8) { + for (j -= (readIndex % 8) ; j > 0 ; j--) { + if (readIndex < max_bits && bitvec_read_field(bv, &readIndex, 1) == b) + temp_res++; + else { + bv->cur_bit--; + return temp_res; + } + } + } + for (i = (readIndex / 8); + i < (remaining_bits ? remaining_bytes + 1 : remaining_bytes); + i++, count++) { + if ((b ? byte_mask : 0) != bv->data[i]) { + bv->cur_bit = (count * 8 + + leading_bits(bv->data[i], b) + readIndex); + return count * 8 + + leading_bits(bv->data[i], b) + temp_res; + } + } + bv->cur_bit = (temp_res + (count * 8)) + readIndex; + if (bv->cur_bit > max_bits) + bv->cur_bit = max_bits; + return (bv->cur_bit - readIndex + temp_res); +} + +/*! Shifts bitvec to the left, n MSB bits lost */ +void bitvec_shiftl(struct bitvec *bv, unsigned n) +{ + if (0 == n) + return; + if (n >= bv->cur_bit) { + bitvec_zero(bv); + return; + } + + memmove(bv->data, bv->data + n / 8, bv->data_len - n / 8); + + uint8_t tmp[2]; + unsigned i; + for (i = 0; i < bv->data_len - 2; i++) { + uint16_t t = osmo_load16be(bv->data + i); + osmo_store16be(t << (n % 8), &tmp); + bv->data[i] = tmp[0]; + } + + bv->data[bv->data_len - 1] <<= (n % 8); + bv->cur_bit -= n; +} + +/*! Add given array to bitvec + * \param[in,out] bv bit vector to work with + * \param[in] array elements to be added + * \param[in] array_len length of array + * \param[in] dry_run indicates whether to return number of bits required + * instead of adding anything to bv for real + * \param[in] num_bits number of bits to consider in each element of array + * \returns number of bits necessary to add array elements if dry_run is true, + * 0 otherwise (only in this case bv is actually changed) + * + * N. B: no length checks are performed on bv - it's caller's job to ensure + * enough space is available - for example by calling with dry_run = true first. + * + * Useful for common pattern in CSN.1 spec which looks like: + * { 1 < XXX : bit (num_bits) > } ** 0 + * which means repeat any times (between 0 and infinity), + * start each repetition with 1, mark end of repetitions with 0 bit + * see app. note in 3GPP TS 24.007 ยง B.2.1 Rule A2 + */ +unsigned int bitvec_add_array(struct bitvec *bv, const uint32_t *array, + unsigned int array_len, bool dry_run, + unsigned int num_bits) +{ + unsigned i, bits = 1; /* account for stop bit */ + for (i = 0; i < array_len; i++) { + if (dry_run) { + bits += (1 + num_bits); + } else { + bitvec_set_bit(bv, 1); + bitvec_set_uint(bv, array[i], num_bits); + } + } + + if (dry_run) + return bits; + + bitvec_set_bit(bv, 0); /* stop bit - end of the sequence */ + return 0; +} + +/*! @} */ diff --git a/lib/decoding/osmocom/core/bitvec.h b/lib/decoding/osmocom/core/bitvec.h new file mode 100644 index 0000000..84db9a5 --- /dev/null +++ b/lib/decoding/osmocom/core/bitvec.h @@ -0,0 +1,87 @@ +/* (C) 2009 by Harald Welte + * (C) 2012 Ivan Klyuchnikov + * (C) 2015 sysmocom - s.f.m.c. GmbH + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * + */ + +#pragma once + +/*! \defgroup bitvec Bit vectors + * @{ + * \file bitvec.h */ + +#include +//#include +#include +#include + +/*! A single GSM bit + * + * In GSM mac blocks, every bit can be 0 or 1, or L or H. L/H are + * defined relative to the 0x2b padding pattern */ +enum bit_value { + ZERO = 0, /*!< A zero (0) bit */ + ONE = 1, /*!< A one (1) bit */ + L = 2, /*!< A CSN.1 "L" bit */ + H = 3, /*!< A CSN.1 "H" bit */ +}; + +/*! structure describing a bit vector */ +struct bitvec { + unsigned int cur_bit; /*!< cursor to the next unused bit */ + unsigned int data_len; /*!< length of data array in bytes */ + uint8_t *data; /*!< pointer to data array */ +}; + +enum bit_value bitvec_get_bit_pos(const struct bitvec *bv, unsigned int bitnr); +enum bit_value bitvec_get_bit_pos_high(const struct bitvec *bv, + unsigned int bitnr); +unsigned int bitvec_get_nth_set_bit(const struct bitvec *bv, unsigned int n); +int bitvec_set_bit_pos(struct bitvec *bv, unsigned int bitnum, + enum bit_value bit); +int bitvec_set_bit(struct bitvec *bv, enum bit_value bit); +int bitvec_get_bit_high(struct bitvec *bv); +int bitvec_set_bits(struct bitvec *bv, const enum bit_value *bits, unsigned int count); +int bitvec_set_u64(struct bitvec *bv, uint64_t v, uint8_t num_bits, bool use_lh); +int bitvec_set_uint(struct bitvec *bv, unsigned int in, unsigned int count); +int bitvec_get_uint(struct bitvec *bv, unsigned int num_bits); +int bitvec_find_bit_pos(const struct bitvec *bv, unsigned int n, enum bit_value val); +int bitvec_spare_padding(struct bitvec *bv, unsigned int up_to_bit); +int bitvec_get_bytes(struct bitvec *bv, uint8_t *bytes, unsigned int count); +int bitvec_set_bytes(struct bitvec *bv, const uint8_t *bytes, unsigned int count); +/*struct bitvec *bitvec_alloc(unsigned int size, TALLOC_CTX *bvctx);*/ +/*void bitvec_free(struct bitvec *bv);*/ +int bitvec_unhex(struct bitvec *bv, const char *src); +unsigned int bitvec_pack(const struct bitvec *bv, uint8_t *buffer); +unsigned int bitvec_unpack(struct bitvec *bv, const uint8_t *buffer); +uint64_t bitvec_read_field(struct bitvec *bv, unsigned int *read_index, unsigned int len); +int bitvec_write_field(struct bitvec *bv, unsigned int *write_index, uint64_t val, unsigned int len); +int bitvec_fill(struct bitvec *bv, unsigned int num_bits, enum bit_value fill); +char bit_value_to_char(enum bit_value v); +void bitvec_to_string_r(const struct bitvec *bv, char *str); +void bitvec_zero(struct bitvec *bv); +unsigned bitvec_rl(const struct bitvec *bv, bool b); +unsigned bitvec_rl_curbit(struct bitvec *bv, bool b, int max_bits); +void bitvec_shiftl(struct bitvec *bv, unsigned int n); +int16_t bitvec_get_int16_msb(const struct bitvec *bv, unsigned int num_bits); +unsigned int bitvec_add_array(struct bitvec *bv, const uint32_t *array, + unsigned int array_len, bool dry_run, + unsigned int num_bits); + +/*! @} */ diff --git a/lib/decoding/osmocom/core/conv.c b/lib/decoding/osmocom/core/conv.c new file mode 100644 index 0000000..e60ce35 --- /dev/null +++ b/lib/decoding/osmocom/core/conv.c @@ -0,0 +1,644 @@ +/*! \file conv.c + * Generic convolutional encoding / decoding. */ +/* + * Copyright (C) 2011 Sylvain Munaut + * + * All Rights Reserved + * + * SPDX-License-Identifier: GPL-2.0+ + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +/*! \addtogroup conv + * @{ + * Osmocom convolutional encoder and decoder. + * + * \file conv.c */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#ifdef HAVE_ALLOCA_H +#include +#endif +#include +#include +#include + +#include +#include + + +/* ------------------------------------------------------------------------ */ +/* Common */ +/* ------------------------------------------------------------------------ */ + +int +osmo_conv_get_input_length(const struct osmo_conv_code *code, int len) +{ + return len <= 0 ? code->len : len; +} + +int +osmo_conv_get_output_length(const struct osmo_conv_code *code, int len) +{ + int pbits, in_len, out_len; + + /* Input length */ + in_len = osmo_conv_get_input_length(code, len); + + /* Output length */ + out_len = in_len * code->N; + + if (code->term == CONV_TERM_FLUSH) + out_len += code->N * (code->K - 1); + + /* Count punctured bits */ + if (code->puncture) { + for (pbits=0; code->puncture[pbits] >= 0; pbits++); + out_len -= pbits; + } + + return out_len; +} + + +/* ------------------------------------------------------------------------ */ +/* Encoding */ +/* ------------------------------------------------------------------------ */ + +/*! Initialize a convolutional encoder + * \param[in,out] encoder Encoder state to initialize + * \param[in] code Description of convolutional code + */ +void +osmo_conv_encode_init(struct osmo_conv_encoder *encoder, + const struct osmo_conv_code *code) +{ + memset(encoder, 0x00, sizeof(struct osmo_conv_encoder)); + encoder->code = code; +} + +void +osmo_conv_encode_load_state(struct osmo_conv_encoder *encoder, + const ubit_t *input) +{ + int i; + uint8_t state = 0; + + for (i=0; i<(encoder->code->K-1); i++) + state = (state << 1) | input[i]; + + encoder->state = state; +} + +static inline int +_conv_encode_do_output(struct osmo_conv_encoder *encoder, + uint8_t out, ubit_t *output) +{ + const struct osmo_conv_code *code = encoder->code; + int o_idx = 0; + int j; + + if (code->puncture) { + for (j=0; jN; j++) + { + int bit_no = code->N - j - 1; + int r_idx = encoder->i_idx * code->N + j; + + if (code->puncture[encoder->p_idx] == r_idx) + encoder->p_idx++; + else + output[o_idx++] = (out >> bit_no) & 1; + } + } else { + for (j=0; jN; j++) + { + int bit_no = code->N - j - 1; + output[o_idx++] = (out >> bit_no) & 1; + } + } + + return o_idx; +} + +int +osmo_conv_encode_raw(struct osmo_conv_encoder *encoder, + const ubit_t *input, ubit_t *output, int n) +{ + const struct osmo_conv_code *code = encoder->code; + uint8_t state; + int i; + int o_idx; + + o_idx = 0; + state = encoder->state; + + for (i=0; inext_output[state][bit]; + state = code->next_state[state][bit]; + + o_idx += _conv_encode_do_output(encoder, out, &output[o_idx]); + + encoder->i_idx++; + } + + encoder->state = state; + + return o_idx; +} + +int +osmo_conv_encode_flush(struct osmo_conv_encoder *encoder, + ubit_t *output) +{ + const struct osmo_conv_code *code = encoder->code; + uint8_t state; + int n; + int i; + int o_idx; + + n = code->K - 1; + + o_idx = 0; + state = encoder->state; + + for (i=0; inext_term_output) { + out = code->next_term_output[state]; + state = code->next_term_state[state]; + } else { + out = code->next_output[state][0]; + state = code->next_state[state][0]; + } + + o_idx += _conv_encode_do_output(encoder, out, &output[o_idx]); + + encoder->i_idx++; + } + + encoder->state = state; + + return o_idx; +} + +/*! All-in-one convolutional encoding function + * \param[in] code description of convolutional code to be used + * \param[in] input array of unpacked bits (uncoded) + * \param[out] output array of unpacked bits (encoded) + * \return Number of produced output bits + * + * This is an all-in-one function, taking care of + * \ref osmo_conv_init, \ref osmo_conv_encode_load_state, + * \ref osmo_conv_encode_raw and \ref osmo_conv_encode_flush as needed. + */ +int +osmo_conv_encode(const struct osmo_conv_code *code, + const ubit_t *input, ubit_t *output) +{ + struct osmo_conv_encoder encoder; + int l; + + osmo_conv_encode_init(&encoder, code); + + if (code->term == CONV_TERM_TAIL_BITING) { + int eidx = code->len - code->K + 1; + osmo_conv_encode_load_state(&encoder, &input[eidx]); + } + + l = osmo_conv_encode_raw(&encoder, input, output, code->len); + + if (code->term == CONV_TERM_FLUSH) + l += osmo_conv_encode_flush(&encoder, &output[l]); + + return l; +} + + +/* ------------------------------------------------------------------------ */ +/* Decoding (viterbi) */ +/* ------------------------------------------------------------------------ */ + +#define MAX_AE 0x00ffffff + +/* Forward declaration for accerlated decoding with certain codes */ +int +osmo_conv_decode_acc(const struct osmo_conv_code *code, + const sbit_t *input, ubit_t *output); + +void +osmo_conv_decode_init(struct osmo_conv_decoder *decoder, + const struct osmo_conv_code *code, int len, int start_state) +{ + int n_states; + + /* Init */ + if (len <= 0) + len = code->len; + + n_states = 1 << (code->K - 1); + + memset(decoder, 0x00, sizeof(struct osmo_conv_decoder)); + + decoder->code = code; + decoder->n_states = n_states; + decoder->len = len; + + /* Allocate arrays */ + decoder->ae = malloc(sizeof(unsigned int) * n_states); + decoder->ae_next = malloc(sizeof(unsigned int) * n_states); + + decoder->state_history = malloc(sizeof(uint8_t) * n_states * (len + decoder->code->K - 1)); + + /* Classic reset */ + osmo_conv_decode_reset(decoder, start_state); +} + +void +osmo_conv_decode_reset(struct osmo_conv_decoder *decoder, int start_state) +{ + int i; + + /* Reset indexes */ + decoder->o_idx = 0; + decoder->p_idx = 0; + + /* Initial error */ + if (start_state < 0) { + /* All states possible */ + memset(decoder->ae, 0x00, sizeof(unsigned int) * decoder->n_states); + } else { + /* Fixed start state */ + for (i=0; in_states; i++) { + decoder->ae[i] = (i == start_state) ? 0 : MAX_AE; + } + } +} + +void +osmo_conv_decode_rewind(struct osmo_conv_decoder *decoder) +{ + int i; + unsigned int min_ae = MAX_AE; + + /* Reset indexes */ + decoder->o_idx = 0; + decoder->p_idx = 0; + + /* Initial error normalize (remove constant) */ + for (i=0; in_states; i++) { + if (decoder->ae[i] < min_ae) + min_ae = decoder->ae[i]; + } + + for (i=0; in_states; i++) + decoder->ae[i] -= min_ae; +} + +void +osmo_conv_decode_deinit(struct osmo_conv_decoder *decoder) +{ + free(decoder->ae); + free(decoder->ae_next); + free(decoder->state_history); + + memset(decoder, 0x00, sizeof(struct osmo_conv_decoder)); +} + +int +osmo_conv_decode_scan(struct osmo_conv_decoder *decoder, + const sbit_t *input, int n) +{ + const struct osmo_conv_code *code = decoder->code; + + int i, s, b, j; + + int n_states; + unsigned int *ae; + unsigned int *ae_next; + uint8_t *state_history; + sbit_t *in_sym; + + int i_idx, p_idx; + + /* Prepare */ + n_states = decoder->n_states; + + ae = decoder->ae; + ae_next = decoder->ae_next; + state_history = &decoder->state_history[n_states * decoder->o_idx]; + + in_sym = malloc(sizeof(sbit_t) * code->N); + + i_idx = 0; + p_idx = decoder->p_idx; + + /* Scan the treillis */ + for (i=0; ipuncture) { + /* Hard way ... */ + for (j=0; jN; j++) { + int idx = ((decoder->o_idx + i) * code->N) + j; + if (idx == code->puncture[p_idx]) { + in_sym[j] = 0; /* Undefined */ + p_idx++; + } else { + in_sym[j] = input[i_idx]; + i_idx++; + } + } + } else { + /* Easy, just copy N bits */ + memcpy(in_sym, &input[i_idx], code->N); + i_idx += code->N; + } + + /* Scan all state */ + for (s=0; snext_output[s][b]; + uint8_t state = code->next_state[s][b]; + + /* New error for this path */ + nae = ae[s]; /* start from last error */ + m = 1 << (code->N - 1); /* mask for 'out' bit selection */ + + for (j=0; jN; j++) { + int is = (int)in_sym[j]; + if (is) { + ov = (out & m) ? -127 : 127; /* sbit_t value for it */ + e = is - ov; /* raw error for this bit */ + nae += (e * e) >> 9; /* acc the squared/scaled value */ + } + m >>= 1; /* next mask bit */ + } + + /* Is it survivor ? */ + if (ae_next[state] > nae) { + ae_next[state] = nae; + state_history[(n_states * i) + state] = s; + } + } + } + + /* Copy accumulated error */ + memcpy(ae, ae_next, sizeof(unsigned int) * n_states); + } + + /* Update decoder state */ + decoder->p_idx = p_idx; + decoder->o_idx += n; + + free(in_sym); + return i_idx; +} + +int +osmo_conv_decode_flush(struct osmo_conv_decoder *decoder, + const sbit_t *input) +{ + const struct osmo_conv_code *code = decoder->code; + + int i, s, j; + + int n_states; + unsigned int *ae; + unsigned int *ae_next; + uint8_t *state_history; + sbit_t *in_sym; + + int i_idx, p_idx; + + /* Prepare */ + n_states = decoder->n_states; + + ae = decoder->ae; + ae_next = decoder->ae_next; + state_history = &decoder->state_history[n_states * decoder->o_idx]; + + in_sym = malloc(sizeof(sbit_t) * code->N); + + i_idx = 0; + p_idx = decoder->p_idx; + + /* Scan the treillis */ + for (i=0; iK-1; i++) + { + /* Reset next accumulated error */ + for (s=0; spuncture) { + /* Hard way ... */ + for (j=0; jN; j++) { + int idx = ((decoder->o_idx + i) * code->N) + j; + if (idx == code->puncture[p_idx]) { + in_sym[j] = 0; /* Undefined */ + p_idx++; + } else { + in_sym[j] = input[i_idx]; + i_idx++; + } + } + } else { + /* Easy, just copy N bits */ + memcpy(in_sym, &input[i_idx], code->N); + i_idx += code->N; + } + + /* Scan all state */ + for (s=0; snext_term_output) { + out = code->next_term_output[s]; + state = code->next_term_state[s]; + } else { + out = code->next_output[s][0]; + state = code->next_state[s][0]; + } + + /* New error for this path */ + nae = ae[s]; /* start from last error */ + m = 1 << (code->N - 1); /* mask for 'out' bit selection */ + + for (j=0; jN; j++) { + int is = (int)in_sym[j]; + if (is) { + ov = (out & m) ? -127 : 127; /* sbit_t value for it */ + e = is - ov; /* raw error for this bit */ + nae += (e * e) >> 9; /* acc the squared/scaled value */ + } + m >>= 1; /* next mask bit */ + } + + /* Is it survivor ? */ + if (ae_next[state] > nae) { + ae_next[state] = nae; + state_history[(n_states * i) + state] = s; + } + } + + /* Copy accumulated error */ + memcpy(ae, ae_next, sizeof(unsigned int) * n_states); + } + + /* Update decoder state */ + decoder->p_idx = p_idx; + decoder->o_idx += code->K - 1; + + free(in_sym); + return i_idx; +} + +int +osmo_conv_decode_get_output(struct osmo_conv_decoder *decoder, + ubit_t *output, int has_flush, int end_state) +{ + const struct osmo_conv_code *code = decoder->code; + + int min_ae; + uint8_t min_state, cur_state; + int i, s, n; + + uint8_t *sh_ptr; + + /* End state ? */ + if (end_state < 0) { + /* Find state with least error */ + min_ae = MAX_AE; + min_state = 0xff; + + for (s=0; sn_states; s++) + { + if (decoder->ae[s] < min_ae) { + min_ae = decoder->ae[s]; + min_state = s; + } + } + + if (min_state == 0xff) + return -1; + } else { + min_state = (uint8_t) end_state; + min_ae = decoder->ae[end_state]; + } + + /* Traceback */ + cur_state = min_state; + + n = decoder->o_idx; + + sh_ptr = &decoder->state_history[decoder->n_states * (n-1)]; + + /* No output for the K-1 termination input bits */ + if (has_flush) { + for (i=0; iK-1; i++) { + cur_state = sh_ptr[cur_state]; + sh_ptr -= decoder->n_states; + } + n -= code->K - 1; + } + + /* Generate output backward */ + for (i=n-1; i>=0; i--) + { + min_state = cur_state; + cur_state = sh_ptr[cur_state]; + + sh_ptr -= decoder->n_states; + + if (code->next_state[cur_state][0] == min_state) + output[i] = 0; + else + output[i] = 1; + } + + return min_ae; +} + +/*! All-in-one convolutional decoding function + * \param[in] code description of convolutional code to be used + * \param[in] input array of soft bits (coded) + * \param[out] output array of unpacked bits (decoded) + * + * This is an all-in-one function, taking care of + * \ref osmo_conv_decode_init, \ref osmo_conv_decode_scan, + * \ref osmo_conv_decode_flush, \ref osmo_conv_decode_get_output and + * \ref osmo_conv_decode_deinit. + */ +int +osmo_conv_decode(const struct osmo_conv_code *code, + const sbit_t *input, ubit_t *output) +{ + struct osmo_conv_decoder decoder; + int rv, l; + + /* Use accelerated implementation for supported codes */ + if ((code->N <= 4) && ((code->K == 5) || (code->K == 7))) + return osmo_conv_decode_acc(code, input, output); + + osmo_conv_decode_init(&decoder, code, 0, 0); + + if (code->term == CONV_TERM_TAIL_BITING) { + osmo_conv_decode_scan(&decoder, input, code->len); + osmo_conv_decode_rewind(&decoder); + } + + l = osmo_conv_decode_scan(&decoder, input, code->len); + + if (code->term == CONV_TERM_FLUSH) + osmo_conv_decode_flush(&decoder, &input[l]); + + rv = osmo_conv_decode_get_output(&decoder, output, + code->term == CONV_TERM_FLUSH, /* has_flush */ + code->term == CONV_TERM_FLUSH ? 0 : -1 /* end_state */ + ); + + osmo_conv_decode_deinit(&decoder); + + return rv; +} + +/*! @} */ diff --git a/lib/decoding/osmocom/core/conv.h b/lib/decoding/osmocom/core/conv.h new file mode 100644 index 0000000..8b344f4 --- /dev/null +++ b/lib/decoding/osmocom/core/conv.h @@ -0,0 +1,139 @@ +/*! \file conv.h + * Osmocom convolutional encoder and decoder. */ +/* + * Copyright (C) 2011 Sylvain Munaut + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +/*! \defgroup conv Convolutional encoding and decoding routines + * @{ + * \file conv.h */ + +#pragma once + +#include + +#include + +/*! possibe termination types + * + * The termination type will determine which state the encoder/decoder + * can start/end with. This is mostly taken care of in the high level API + * call. So if you use the low level API, you must take care of making the + * proper calls yourself. + */ +enum osmo_conv_term { + CONV_TERM_FLUSH = 0, /*!< Flush encoder state */ + CONV_TERM_TRUNCATION, /*!< Direct truncation */ + CONV_TERM_TAIL_BITING, /*!< Tail biting */ +}; + +/*! structure describing a given convolutional code + * + * The only required fields are N,K and the next_output/next_state arrays. The + * other can be left to default value of zero depending on what the code does. + * If 'len' is left at 0 then only the low level API can be used. + */ +struct osmo_conv_code { + int N; /*!< Inverse of code rate */ + int K; /*!< Constraint length */ + int len; /*!< # of data bits */ + + enum osmo_conv_term term; /*!< Termination type */ + + const uint8_t (*next_output)[2];/*!< Next output array */ + const uint8_t (*next_state)[2]; /*!< Next state array */ + + const uint8_t *next_term_output;/*!< Flush termination output */ + const uint8_t *next_term_state; /*!< Flush termination state */ + + const int *puncture; /*!< Punctured bits indexes */ +}; + + +/* Common */ + +int osmo_conv_get_input_length(const struct osmo_conv_code *code, int len); +int osmo_conv_get_output_length(const struct osmo_conv_code *code, int len); + + +/* Encoding */ + + /* Low level API */ + +/*! convolutional encoder state */ +struct osmo_conv_encoder { + const struct osmo_conv_code *code; /*!< for which code? */ + int i_idx; /*!< Next input bit index */ + int p_idx; /*!< Current puncture index */ + uint8_t state; /*!< Current state */ +}; + +void osmo_conv_encode_init(struct osmo_conv_encoder *encoder, + const struct osmo_conv_code *code); +void osmo_conv_encode_load_state(struct osmo_conv_encoder *encoder, + const ubit_t *input); +int osmo_conv_encode_raw(struct osmo_conv_encoder *encoder, + const ubit_t *input, ubit_t *output, int n); +int osmo_conv_encode_flush(struct osmo_conv_encoder *encoder, ubit_t *output); + + /* All-in-one */ +int osmo_conv_encode(const struct osmo_conv_code *code, + const ubit_t *input, ubit_t *output); + + +/* Decoding */ + + /* Low level API */ + +/*! convolutional decoder state */ +struct osmo_conv_decoder { + const struct osmo_conv_code *code; /*!< for which code? */ + + int n_states; /*!< number of states */ + + int len; /*!< Max o_idx (excl. termination) */ + + int o_idx; /*!< output index */ + int p_idx; /*!< puncture index */ + + unsigned int *ae; /*!< accumulated error */ + unsigned int *ae_next; /*!< next accumulated error (tmp in scan) */ + uint8_t *state_history; /*!< state history [len][n_states] */ +}; + +void osmo_conv_decode_init(struct osmo_conv_decoder *decoder, + const struct osmo_conv_code *code, + int len, int start_state); +void osmo_conv_decode_reset(struct osmo_conv_decoder *decoder, int start_state); +void osmo_conv_decode_rewind(struct osmo_conv_decoder *decoder); +void osmo_conv_decode_deinit(struct osmo_conv_decoder *decoder); + +int osmo_conv_decode_scan(struct osmo_conv_decoder *decoder, + const sbit_t *input, int n); +int osmo_conv_decode_flush(struct osmo_conv_decoder *decoder, + const sbit_t *input); +int osmo_conv_decode_get_output(struct osmo_conv_decoder *decoder, + ubit_t *output, int has_flush, int end_state); + + /* All-in-one */ +int osmo_conv_decode(const struct osmo_conv_code *code, + const sbit_t *input, ubit_t *output); + + +/*! @} */ diff --git a/lib/decoding/osmocom/core/conv_acc.c b/lib/decoding/osmocom/core/conv_acc.c new file mode 100644 index 0000000..dce2682 --- /dev/null +++ b/lib/decoding/osmocom/core/conv_acc.c @@ -0,0 +1,720 @@ +/*! \file conv_acc.c + * Accelerated Viterbi decoder implementation. */ +/* + * Copyright (C) 2013, 2014 Thomas Tsou + * + * All Rights Reserved + * + * SPDX-License-Identifier: GPL-2.0+ + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include +#include +#include + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#define __attribute__(_arg_) + +#include + +#define BIT2NRZ(REG,N) (((REG >> N) & 0x01) * 2 - 1) * -1 +#define NUM_STATES(K) (K == 7 ? 64 : 16) + +#define INIT_POINTERS(simd) \ +{ \ + osmo_conv_metrics_k5_n2 = osmo_conv_##simd##_metrics_k5_n2; \ + osmo_conv_metrics_k5_n3 = osmo_conv_##simd##_metrics_k5_n3; \ + osmo_conv_metrics_k5_n4 = osmo_conv_##simd##_metrics_k5_n4; \ + osmo_conv_metrics_k7_n2 = osmo_conv_##simd##_metrics_k7_n2; \ + osmo_conv_metrics_k7_n3 = osmo_conv_##simd##_metrics_k7_n3; \ + osmo_conv_metrics_k7_n4 = osmo_conv_##simd##_metrics_k7_n4; \ + vdec_malloc = &osmo_conv_##simd##_vdec_malloc; \ + vdec_free = &osmo_conv_##simd##_vdec_free; \ +} + +static int init_complete = 0; + +__attribute__ ((visibility("hidden"))) int avx2_supported = 0; +__attribute__ ((visibility("hidden"))) int ssse3_supported = 0; +__attribute__ ((visibility("hidden"))) int sse41_supported = 0; + +/** + * These pointers are being initialized at runtime by the + * osmo_conv_init() depending on supported SIMD extensions. + */ +static int16_t *(*vdec_malloc)(size_t n); +static void (*vdec_free)(int16_t *ptr); + +void (*osmo_conv_metrics_k5_n2)(const int8_t *seq, + const int16_t *out, int16_t *sums, int16_t *paths, int norm); +void (*osmo_conv_metrics_k5_n3)(const int8_t *seq, + const int16_t *out, int16_t *sums, int16_t *paths, int norm); +void (*osmo_conv_metrics_k5_n4)(const int8_t *seq, + const int16_t *out, int16_t *sums, int16_t *paths, int norm); +void (*osmo_conv_metrics_k7_n2)(const int8_t *seq, + const int16_t *out, int16_t *sums, int16_t *paths, int norm); +void (*osmo_conv_metrics_k7_n3)(const int8_t *seq, + const int16_t *out, int16_t *sums, int16_t *paths, int norm); +void (*osmo_conv_metrics_k7_n4)(const int8_t *seq, + const int16_t *out, int16_t *sums, int16_t *paths, int norm); + +/* Forward malloc wrappers */ +int16_t *osmo_conv_gen_vdec_malloc(size_t n); +void osmo_conv_gen_vdec_free(int16_t *ptr); + +#if defined(HAVE_SSSE3) +int16_t *osmo_conv_sse_vdec_malloc(size_t n); +void osmo_conv_sse_vdec_free(int16_t *ptr); +#endif + +#if defined(HAVE_SSSE3) && defined(HAVE_AVX2) +int16_t *osmo_conv_sse_avx_vdec_malloc(size_t n); +void osmo_conv_sse_avx_vdec_free(int16_t *ptr); +#endif + +/* Forward Metric Units */ +void osmo_conv_gen_metrics_k5_n2(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_gen_metrics_k5_n3(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_gen_metrics_k5_n4(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_gen_metrics_k7_n2(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_gen_metrics_k7_n3(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_gen_metrics_k7_n4(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); + +#if defined(HAVE_SSSE3) +void osmo_conv_sse_metrics_k5_n2(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_sse_metrics_k5_n3(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_sse_metrics_k5_n4(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_sse_metrics_k7_n2(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_sse_metrics_k7_n3(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_sse_metrics_k7_n4(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +#endif + +#if defined(HAVE_SSSE3) && defined(HAVE_AVX2) +void osmo_conv_sse_avx_metrics_k5_n2(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_sse_avx_metrics_k5_n3(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_sse_avx_metrics_k5_n4(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_sse_avx_metrics_k7_n2(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_sse_avx_metrics_k7_n3(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +void osmo_conv_sse_avx_metrics_k7_n4(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm); +#endif + +/* Trellis State + * state - Internal lshift register value + * prev - Register values of previous 0 and 1 states + */ +struct vstate { + unsigned state; + unsigned prev[2]; +}; + +/* Trellis Object + * num_states - Number of states in the trellis + * sums - Accumulated path metrics + * outputs - Trellis output values + * vals - Input value that led to each state + */ +struct vtrellis { + int num_states; + int16_t *sums; + int16_t *outputs; + uint8_t *vals; +}; + +/* Viterbi Decoder + * n - Code order + * k - Constraint length + * len - Horizontal length of trellis + * recursive - Set to '1' if the code is recursive + * intrvl - Normalization interval + * trellis - Trellis object + * paths - Trellis paths + */ +struct vdecoder { + int n; + int k; + int len; + int recursive; + int intrvl; + struct vtrellis trellis; + int16_t **paths; + + void (*metric_func)(const int8_t *, const int16_t *, + int16_t *, int16_t *, int); +}; + +/* Accessor calls */ +static inline int conv_code_recursive(const struct osmo_conv_code *code) +{ + return code->next_term_output ? 1 : 0; +} + +/* Left shift and mask for finding the previous state */ +static unsigned vstate_lshift(unsigned reg, int k, int val) +{ + unsigned mask; + + if (k == 5) + mask = 0x0e; + else if (k == 7) + mask = 0x3e; + else + mask = 0; + + return ((reg << 1) & mask) | val; +} + +/* Bit endian manipulators */ +static inline unsigned bitswap2(unsigned v) +{ + return ((v & 0x02) >> 1) | ((v & 0x01) << 1); +} + +static inline unsigned bitswap3(unsigned v) +{ + return ((v & 0x04) >> 2) | ((v & 0x02) >> 0) | + ((v & 0x01) << 2); +} + +static inline unsigned bitswap4(unsigned v) +{ + return ((v & 0x08) >> 3) | ((v & 0x04) >> 1) | + ((v & 0x02) << 1) | ((v & 0x01) << 3); +} + +static inline unsigned bitswap5(unsigned v) +{ + return ((v & 0x10) >> 4) | ((v & 0x08) >> 2) | ((v & 0x04) >> 0) | + ((v & 0x02) << 2) | ((v & 0x01) << 4); +} + +static inline unsigned bitswap6(unsigned v) +{ + return ((v & 0x20) >> 5) | ((v & 0x10) >> 3) | ((v & 0x08) >> 1) | + ((v & 0x04) << 1) | ((v & 0x02) << 3) | ((v & 0x01) << 5); +} + +static unsigned bitswap(unsigned v, unsigned n) +{ + switch (n) { + case 1: + return v; + case 2: + return bitswap2(v); + case 3: + return bitswap3(v); + case 4: + return bitswap4(v); + case 5: + return bitswap5(v); + case 6: + return bitswap6(v); + default: + return 0; + } +} + +/* Generate non-recursive state output from generator state table + * Note that the shift register moves right (i.e. the most recent bit is + * shifted into the register at k-1 bit of the register), which is typical + * textbook representation. The API transition table expects the most recent + * bit in the low order bit, or left shift. A bitswap operation is required + * to accommodate the difference. + */ +static unsigned gen_output(struct vstate *state, int val, + const struct osmo_conv_code *code) +{ + unsigned out, prev; + + prev = bitswap(state->prev[0], code->K - 1); + out = code->next_output[prev][val]; + out = bitswap(out, code->N); + + return out; +} + +/* Populate non-recursive trellis state + * For a given state defined by the k-1 length shift register, find the + * value of the input bit that drove the trellis to that state. Also + * generate the N outputs of the generator polynomial at that state. + */ +static int gen_state_info(uint8_t *val, unsigned reg, + int16_t *output, const struct osmo_conv_code *code) +{ + int i; + unsigned out; + struct vstate state; + + /* Previous '0' state */ + state.state = reg; + state.prev[0] = vstate_lshift(reg, code->K, 0); + state.prev[1] = vstate_lshift(reg, code->K, 1); + + *val = (reg >> (code->K - 2)) & 0x01; + + /* Transition output */ + out = gen_output(&state, *val, code); + + /* Unpack to NRZ */ + for (i = 0; i < code->N; i++) + output[i] = BIT2NRZ(out, i); + + return 0; +} + +/* Generate recursive state output from generator state table */ +static unsigned gen_recursive_output(struct vstate *state, + uint8_t *val, unsigned reg, + const struct osmo_conv_code *code, int pos) +{ + int val0, val1; + unsigned out, prev; + + /* Previous '0' state */ + prev = vstate_lshift(reg, code->K, 0); + prev = bitswap(prev, code->K - 1); + + /* Input value */ + val0 = (reg >> (code->K - 2)) & 0x01; + val1 = (code->next_term_output[prev] >> pos) & 0x01; + *val = val0 == val1 ? 0 : 1; + + /* Wrapper for osmocom state access */ + prev = bitswap(state->prev[0], code->K - 1); + + /* Compute the transition output */ + out = code->next_output[prev][*val]; + out = bitswap(out, code->N); + + return out; +} + +/* Populate recursive trellis state + * The bit position of the systematic bit is not explicitly marked by the + * API, so it must be extracted from the generator table. Otherwise, + * populate the trellis similar to the non-recursive version. + * Non-systematic recursive codes are not supported. + */ +static int gen_recursive_state_info(uint8_t *val, + unsigned reg, int16_t *output, const struct osmo_conv_code *code) +{ + int i, j, pos = -1; + int ns = NUM_STATES(code->K); + unsigned out; + struct vstate state; + + /* Previous '0' and '1' states */ + state.state = reg; + state.prev[0] = vstate_lshift(reg, code->K, 0); + state.prev[1] = vstate_lshift(reg, code->K, 1); + + /* Find recursive bit location */ + for (i = 0; i < code->N; i++) { + for (j = 0; j < ns; j++) { + if ((code->next_output[j][0] >> i) & 0x01) + break; + } + + if (j == ns) { + pos = i; + break; + } + } + + /* Non-systematic recursive code not supported */ + if (pos < 0) + return -EPROTO; + + /* Transition output */ + out = gen_recursive_output(&state, val, reg, code, pos); + + /* Unpack to NRZ */ + for (i = 0; i < code->N; i++) + output[i] = BIT2NRZ(out, i); + + return 0; +} + +/* Release the trellis */ +static void free_trellis(struct vtrellis *trellis) +{ + if (!trellis) + return; + + vdec_free(trellis->outputs); + vdec_free(trellis->sums); + free(trellis->vals); +} + +/* Initialize the trellis object + * Initialization consists of generating the outputs and output value of a + * given state. Due to trellis symmetry and anti-symmetry, only one of the + * transition paths is utilized by the butterfly operation in the forward + * recursion, so only one set of N outputs is required per state variable. + */ +static int generate_trellis(struct vdecoder *dec, + const struct osmo_conv_code *code) +{ + struct vtrellis *trellis = &dec->trellis; + int16_t *outputs; + int i, rc; + + int ns = NUM_STATES(code->K); + int olen = (code->N == 2) ? 2 : 4; + + trellis->num_states = ns; + trellis->sums = vdec_malloc(ns); + trellis->outputs = vdec_malloc(ns * olen); + trellis->vals = (uint8_t *) malloc(ns * sizeof(uint8_t)); + + if (!trellis->sums || !trellis->outputs || !trellis->vals) { + rc = -ENOMEM; + goto fail; + } + + /* Populate the trellis state objects */ + for (i = 0; i < ns; i++) { + outputs = &trellis->outputs[olen * i]; + if (dec->recursive) { + rc = gen_recursive_state_info(&trellis->vals[i], + i, outputs, code); + } else { + rc = gen_state_info(&trellis->vals[i], + i, outputs, code); + } + + if (rc < 0) + goto fail; + + /* Set accumulated path metrics to zero */ + trellis->sums[i] = 0; + } + + /** + * For termination other than tail-biting, initialize the zero state + * as the encoder starting state. Initialize with the maximum + * accumulated sum at length equal to the constraint length. + */ + if (code->term != CONV_TERM_TAIL_BITING) + trellis->sums[0] = INT8_MAX * code->N * code->K; + + return 0; + +fail: + free_trellis(trellis); + return rc; +} + +static void _traceback(struct vdecoder *dec, + unsigned state, uint8_t *out, int len) +{ + int i; + unsigned path; + + for (i = len - 1; i >= 0; i--) { + path = dec->paths[i][state] + 1; + out[i] = dec->trellis.vals[state]; + state = vstate_lshift(state, dec->k, path); + } +} + +static void _traceback_rec(struct vdecoder *dec, + unsigned state, uint8_t *out, int len) +{ + int i; + unsigned path; + + for (i = len - 1; i >= 0; i--) { + path = dec->paths[i][state] + 1; + out[i] = path ^ dec->trellis.vals[state]; + state = vstate_lshift(state, dec->k, path); + } +} + +/* Traceback and generate decoded output + * Find the largest accumulated path metric at the final state except for + * the zero terminated case, where we assume the final state is always zero. + */ +static int traceback(struct vdecoder *dec, uint8_t *out, int term, int len) +{ + int i, sum, max = -1; + unsigned path, state = 0; + + if (term != CONV_TERM_FLUSH) { + for (i = 0; i < dec->trellis.num_states; i++) { + sum = dec->trellis.sums[i]; + if (sum > max) { + max = sum; + state = i; + } + } + + if (max < 0) + return -EPROTO; + } + + for (i = dec->len - 1; i >= len; i--) { + path = dec->paths[i][state] + 1; + state = vstate_lshift(state, dec->k, path); + } + + if (dec->recursive) + _traceback_rec(dec, state, out, len); + else + _traceback(dec, state, out, len); + + return 0; +} + +/* Release decoder object */ +static void vdec_deinit(struct vdecoder *dec) +{ + if (!dec) + return; + + free_trellis(&dec->trellis); + + if (dec->paths != NULL) { + vdec_free(dec->paths[0]); + free(dec->paths); + } +} + +/* Initialize decoder object with code specific params + * Subtract the constraint length K on the normalization interval to + * accommodate the initialization path metric at state zero. + */ +static int vdec_init(struct vdecoder *dec, const struct osmo_conv_code *code) +{ + int i, ns, rc; + + ns = NUM_STATES(code->K); + + dec->n = code->N; + dec->k = code->K; + dec->recursive = conv_code_recursive(code); + dec->intrvl = INT16_MAX / (dec->n * INT8_MAX) - dec->k; + + if (dec->k == 5) { + switch (dec->n) { + case 2: + dec->metric_func = osmo_conv_metrics_k5_n2; + break; + case 3: + dec->metric_func = osmo_conv_metrics_k5_n3; + break; + case 4: + dec->metric_func = osmo_conv_metrics_k5_n4; + break; + default: + return -EINVAL; + } + } else if (dec->k == 7) { + switch (dec->n) { + case 2: + dec->metric_func = osmo_conv_metrics_k7_n2; + break; + case 3: + dec->metric_func = osmo_conv_metrics_k7_n3; + break; + case 4: + dec->metric_func = osmo_conv_metrics_k7_n4; + break; + default: + return -EINVAL; + } + } else { + return -EINVAL; + } + + if (code->term == CONV_TERM_FLUSH) + dec->len = code->len + code->K - 1; + else + dec->len = code->len; + + rc = generate_trellis(dec, code); + if (rc) + return rc; + + dec->paths = (int16_t **) malloc(sizeof(int16_t *) * dec->len); + if (!dec->paths) + goto enomem; + + dec->paths[0] = vdec_malloc(ns * dec->len); + if (!dec->paths[0]) + goto enomem; + + for (i = 1; i < dec->len; i++) + dec->paths[i] = &dec->paths[0][i * ns]; + + return 0; + +enomem: + vdec_deinit(dec); + return -ENOMEM; +} + +/* Depuncture sequence with nagative value terminated puncturing matrix */ +static int depuncture(const int8_t *in, const int *punc, int8_t *out, int len) +{ + int i, n = 0, m = 0; + + for (i = 0; i < len; i++) { + if (i == punc[n]) { + out[i] = 0; + n++; + continue; + } + + out[i] = in[m++]; + } + + return 0; +} + +/* Forward trellis recursion + * Generate branch metrics and path metrics with a combined function. Only + * accumulated path metric sums and path selections are stored. Normalize on + * the interval specified by the decoder. + */ +static void forward_traverse(struct vdecoder *dec, const int8_t *seq) +{ + int i; + + for (i = 0; i < dec->len; i++) { + dec->metric_func(&seq[dec->n * i], + dec->trellis.outputs, + dec->trellis.sums, + dec->paths[i], + !(i % dec->intrvl)); + } +} + +/* Convolutional decode with a decoder object + * Initial puncturing run if necessary followed by the forward recursion. + * For tail-biting perform a second pass before running the backward + * traceback operation. + */ +static int conv_decode(struct vdecoder *dec, const int8_t *seq, + const int *punc, uint8_t *out, int len, int term) +{ + //int8_t depunc[dec->len * dec->n]; //!! this isn't portable, in strict C you can't use size of an array that is not known at compile time + int8_t * depunc = malloc(sizeof(int8_t)*dec->len * dec->n); + + + if (punc) { + depuncture(seq, punc, depunc, dec->len * dec->n); + seq = depunc; + } + + /* Propagate through the trellis with interval normalization */ + forward_traverse(dec, seq); + + if (term == CONV_TERM_TAIL_BITING) + forward_traverse(dec, seq); + + free(depunc); + return traceback(dec, out, term, len); +} + +static void osmo_conv_init(void) +{ + init_complete = 1; + +#ifdef HAVE___BUILTIN_CPU_SUPPORTS + /* Detect CPU capabilities */ + #ifdef HAVE_AVX2 + avx2_supported = __builtin_cpu_supports("avx2"); + #endif + + #ifdef HAVE_SSSE3 + ssse3_supported = __builtin_cpu_supports("ssse3"); + #endif + + #ifdef HAVE_SSE4_1 + sse41_supported = __builtin_cpu_supports("sse4.1"); + #endif +#endif + +/** + * Usage of curly braces is mandatory, + * because we use multi-line define. + */ +#if defined(HAVE_SSSE3) && defined(HAVE_AVX2) + if (ssse3_supported && avx2_supported) { + INIT_POINTERS(sse_avx); + } else if (ssse3_supported) { + INIT_POINTERS(sse); + } else { + INIT_POINTERS(gen); + } +#elif defined(HAVE_SSSE3) + if (ssse3_supported) { + INIT_POINTERS(sse); + } else { + INIT_POINTERS(gen); + } +#else + INIT_POINTERS(gen); +#endif +} + +/* All-in-one Viterbi decoding */ +int osmo_conv_decode_acc(const struct osmo_conv_code *code, + const sbit_t *input, ubit_t *output) +{ + int rc; + struct vdecoder dec; + + if (!init_complete) + osmo_conv_init(); + + if ((code->N < 2) || (code->N > 4) || (code->len < 1) || + ((code->K != 5) && (code->K != 7))) + return -EINVAL; + + rc = vdec_init(&dec, code); + if (rc) + return rc; + + rc = conv_decode(&dec, input, code->puncture, + output, code->len, code->term); + + vdec_deinit(&dec); + + return rc; +} diff --git a/lib/decoding/osmocom/core/conv_acc_generic.c b/lib/decoding/osmocom/core/conv_acc_generic.c new file mode 100644 index 0000000..7da0213 --- /dev/null +++ b/lib/decoding/osmocom/core/conv_acc_generic.c @@ -0,0 +1,213 @@ +/*! \file conv_acc_generic.c + * Accelerated Viterbi decoder implementation + * for generic architectures without SSE support. */ +/* + * Copyright (C) 2013, 2014 Thomas Tsou + * + * All Rights Reserved + * + * SPDX-License-Identifier: GPL-2.0+ + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include +#include +#include + +#define __attribute__(_arg_) + +/* Add-Compare-Select (ACS-Butterfly) + * Compute 4 accumulated path metrics and 4 path selections. Note that path + * selections are store as -1 and 0 rather than 0 and 1. This is to match + * the output format of the SSE packed compare instruction 'pmaxuw'. + */ + +static void acs_butterfly(int state, int num_states, + int16_t metric, int16_t *sum, + int16_t *new_sum, int16_t *path) +{ + int state0, state1; + int sum0, sum1, sum2, sum3; + + state0 = *(sum + (2 * state + 0)); + state1 = *(sum + (2 * state + 1)); + + sum0 = state0 + metric; + sum1 = state1 - metric; + sum2 = state0 - metric; + sum3 = state1 + metric; + + if (sum0 >= sum1) { + *new_sum = sum0; + *path = -1; + } else { + *new_sum = sum1; + *path = 0; + } + + if (sum2 >= sum3) { + *(new_sum + num_states / 2) = sum2; + *(path + num_states / 2) = -1; + } else { + *(new_sum + num_states / 2) = sum3; + *(path + num_states / 2) = 0; + } +} + +/* Branch metrics unit N=2 */ +static void gen_branch_metrics_n2(int num_states, const int8_t *seq, + const int16_t *out, int16_t *metrics) +{ + int i; + + for (i = 0; i < num_states / 2; i++) { + metrics[i] = seq[0] * out[2 * i + 0] + + seq[1] * out[2 * i + 1]; + } +} + +/* Branch metrics unit N=3 */ +static void gen_branch_metrics_n3(int num_states, const int8_t *seq, + const int16_t *out, int16_t *metrics) +{ + int i; + + for (i = 0; i < num_states / 2; i++) { + metrics[i] = seq[0] * out[4 * i + 0] + + seq[1] * out[4 * i + 1] + + seq[2] * out[4 * i + 2]; + } +} + +/* Branch metrics unit N=4 */ +static void gen_branch_metrics_n4(int num_states, const int8_t *seq, + const int16_t *out, int16_t *metrics) +{ + int i; + + for (i = 0; i < num_states / 2; i++) { + metrics[i] = seq[0] * out[4 * i + 0] + + seq[1] * out[4 * i + 1] + + seq[2] * out[4 * i + 2] + + seq[3] * out[4 * i + 3]; + } +} + +/* Path metric unit */ +static void gen_path_metrics(int num_states, int16_t *sums, + int16_t *metrics, int16_t *paths, int norm) +{ + int i; + int16_t min; + int16_t * new_sums = malloc(sizeof(int16_t)*num_states); + + for (i = 0; i < num_states / 2; i++) + acs_butterfly(i, num_states, metrics[i], + sums, &new_sums[i], &paths[i]); + + if (norm) { + min = new_sums[0]; + + for (i = 1; i < num_states; i++) + if (new_sums[i] < min) + min = new_sums[i]; + + for (i = 0; i < num_states; i++) + new_sums[i] -= min; + } + + free(new_sums); + memcpy(sums, new_sums, num_states * sizeof(int16_t)); +} + +/* Not-aligned Memory Allocator */ +__attribute__ ((visibility("hidden"))) +int16_t *osmo_conv_gen_vdec_malloc(size_t n) +{ + return (int16_t *) malloc(sizeof(int16_t) * n); +} + +__attribute__ ((visibility("hidden"))) +void osmo_conv_gen_vdec_free(int16_t *ptr) +{ + free(ptr); +} + +/* 16-state branch-path metrics units (K=5) */ +__attribute__ ((visibility("hidden"))) +void osmo_conv_gen_metrics_k5_n2(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm) +{ + int16_t metrics[8]; + + gen_branch_metrics_n2(16, seq, out, metrics); + gen_path_metrics(16, sums, metrics, paths, norm); +} + +__attribute__ ((visibility("hidden"))) +void osmo_conv_gen_metrics_k5_n3(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm) +{ + int16_t metrics[8]; + + gen_branch_metrics_n3(16, seq, out, metrics); + gen_path_metrics(16, sums, metrics, paths, norm); + +} + +__attribute__ ((visibility("hidden"))) +void osmo_conv_gen_metrics_k5_n4(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm) +{ + int16_t metrics[8]; + + gen_branch_metrics_n4(16, seq, out, metrics); + gen_path_metrics(16, sums, metrics, paths, norm); + +} + +/* 64-state branch-path metrics units (K=7) */ +__attribute__ ((visibility("hidden"))) +void osmo_conv_gen_metrics_k7_n2(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm) +{ + int16_t metrics[32]; + + gen_branch_metrics_n2(64, seq, out, metrics); + gen_path_metrics(64, sums, metrics, paths, norm); + +} + +__attribute__ ((visibility("hidden"))) +void osmo_conv_gen_metrics_k7_n3(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm) +{ + int16_t metrics[32]; + + gen_branch_metrics_n3(64, seq, out, metrics); + gen_path_metrics(64, sums, metrics, paths, norm); + +} + +__attribute__ ((visibility("hidden"))) +void osmo_conv_gen_metrics_k7_n4(const int8_t *seq, const int16_t *out, + int16_t *sums, int16_t *paths, int norm) +{ + int16_t metrics[32]; + + gen_branch_metrics_n4(64, seq, out, metrics); + gen_path_metrics(64, sums, metrics, paths, norm); +} diff --git a/lib/decoding/osmocom/core/crc16gen.c b/lib/decoding/osmocom/core/crc16gen.c new file mode 100644 index 0000000..ea69d88 --- /dev/null +++ b/lib/decoding/osmocom/core/crc16gen.c @@ -0,0 +1,120 @@ +/* + * crc16gen.c + * + * Generic CRC routines (for max 16 bits poly) + * + * Copyright (C) 2011 Sylvain Munaut + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +/*! \addtogroup crcgen + * @{ + */ + +/*! \file crc16gen.c + * Osmocom generic CRC routines (for max 16 bits poly) + */ + +#include + +#include +#include + + +/*! \brief Compute the CRC value of a given array of hard-bits + * \param[in] code The CRC code description to apply + * \param[in] in Array of hard bits + * \param[in] len Length of the array of hard bits + * \returns The CRC value + */ +uint16_t +osmo_crc16gen_compute_bits(const struct osmo_crc16gen_code *code, + const ubit_t *in, int len) +{ + const uint16_t poly = code->poly; + uint16_t crc = code->init; + int i, n = code->bits-1; + + for (i=0; ibits) - 1; + } + + crc ^= code->remainder; + + return crc; +} + + +/*! \brief Checks the CRC value of a given array of hard-bits + * \param[in] code The CRC code description to apply + * \param[in] in Array of hard bits + * \param[in] len Length of the array of hard bits + * \param[in] crc_bits Array of hard bits with the alleged CRC + * \returns 0 if CRC matches. 1 in case of error. + * + * The crc_bits array must have a length of code->len + */ +int +osmo_crc16gen_check_bits(const struct osmo_crc16gen_code *code, + const ubit_t *in, int len, const ubit_t *crc_bits) +{ + uint16_t crc; + int i; + + crc = osmo_crc16gen_compute_bits(code, in, len); + + for (i=0; ibits; i++) + if (crc_bits[i] ^ ((crc >> (code->bits-i-1)) & 1)) + return 1; + + return 0; +} + + +/*! \brief Computes and writes the CRC value of a given array of bits + * \param[in] code The CRC code description to apply + * \param[in] in Array of hard bits + * \param[in] len Length of the array of hard bits + * \param[in] crc_bits Array of hard bits to write the computed CRC to + * + * The crc_bits array must have a length of code->len + */ +void +osmo_crc16gen_set_bits(const struct osmo_crc16gen_code *code, + const ubit_t *in, int len, ubit_t *crc_bits) +{ + uint16_t crc; + int i; + + crc = osmo_crc16gen_compute_bits(code, in, len); + + for (i=0; ibits; i++) + crc_bits[i] = ((crc >> (code->bits-i-1)) & 1); +} + +/*! @} */ + +/* vim: set syntax=c: */ diff --git a/lib/decoding/osmocom/core/crc16gen.h b/lib/decoding/osmocom/core/crc16gen.h new file mode 100644 index 0000000..567b74e --- /dev/null +++ b/lib/decoding/osmocom/core/crc16gen.h @@ -0,0 +1,56 @@ +/* + * crc16gen.h + * + * Copyright (C) 2011 Sylvain Munaut + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#pragma once + +/*! \addtogroup crcgen + * @{ + */ + +/*! \file crc16gen.h + * Osmocom generic CRC routines (for max 16 bits poly) header + */ + + +#include +#include + + +/*! \brief structure describing a given CRC code of max 16 bits */ +struct osmo_crc16gen_code { + int bits; /*!< \brief Actual number of bits of the CRC */ + uint16_t poly; /*!< \brief Polynom (normal representation, MSB omitted */ + uint16_t init; /*!< \brief Initialization value of the CRC state */ + uint16_t remainder; /*!< \brief Remainder of the CRC (final XOR) */ +}; + +uint16_t osmo_crc16gen_compute_bits(const struct osmo_crc16gen_code *code, + const ubit_t *in, int len); +int osmo_crc16gen_check_bits(const struct osmo_crc16gen_code *code, + const ubit_t *in, int len, const ubit_t *crc_bits); +void osmo_crc16gen_set_bits(const struct osmo_crc16gen_code *code, + const ubit_t *in, int len, ubit_t *crc_bits); + + +/*! @} */ + +/* vim: set syntax=c: */ diff --git a/lib/decoding/osmocom/core/crc32gen.h b/lib/decoding/osmocom/core/crc32gen.h new file mode 100644 index 0000000..3b95338 --- /dev/null +++ b/lib/decoding/osmocom/core/crc32gen.h @@ -0,0 +1,56 @@ +/* + * crc32gen.h + * + * Copyright (C) 2011 Sylvain Munaut + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#pragma once + +/*! \addtogroup crcgen + * @{ + */ + +/*! \file crc32gen.h + * Osmocom generic CRC routines (for max 32 bits poly) header + */ + + +#include +#include + + +/*! \brief structure describing a given CRC code of max 32 bits */ +struct osmo_crc32gen_code { + int bits; /*!< \brief Actual number of bits of the CRC */ + uint32_t poly; /*!< \brief Polynom (normal representation, MSB omitted */ + uint32_t init; /*!< \brief Initialization value of the CRC state */ + uint32_t remainder; /*!< \brief Remainder of the CRC (final XOR) */ +}; + +uint32_t osmo_crc32gen_compute_bits(const struct osmo_crc32gen_code *code, + const ubit_t *in, int len); +int osmo_crc32gen_check_bits(const struct osmo_crc32gen_code *code, + const ubit_t *in, int len, const ubit_t *crc_bits); +void osmo_crc32gen_set_bits(const struct osmo_crc32gen_code *code, + const ubit_t *in, int len, ubit_t *crc_bits); + + +/*! @} */ + +/* vim: set syntax=c: */ diff --git a/lib/decoding/osmocom/core/crc64gen.c b/lib/decoding/osmocom/core/crc64gen.c new file mode 100644 index 0000000..3e700d4 --- /dev/null +++ b/lib/decoding/osmocom/core/crc64gen.c @@ -0,0 +1,120 @@ +/* + * crc64gen.c + * + * Generic CRC routines (for max 64 bits poly) + * + * Copyright (C) 2011 Sylvain Munaut + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +/*! \addtogroup crcgen + * @{ + */ + +/*! \file crc64gen.c + * Osmocom generic CRC routines (for max 64 bits poly) + */ + +#include + +#include +#include + + +/*! \brief Compute the CRC value of a given array of hard-bits + * \param[in] code The CRC code description to apply + * \param[in] in Array of hard bits + * \param[in] len Length of the array of hard bits + * \returns The CRC value + */ +uint64_t +osmo_crc64gen_compute_bits(const struct osmo_crc64gen_code *code, + const ubit_t *in, int len) +{ + const uint64_t poly = code->poly; + uint64_t crc = code->init; + int i, n = code->bits-1; + + for (i=0; ibits) - 1; + } + + crc ^= code->remainder; + + return crc; +} + + +/*! \brief Checks the CRC value of a given array of hard-bits + * \param[in] code The CRC code description to apply + * \param[in] in Array of hard bits + * \param[in] len Length of the array of hard bits + * \param[in] crc_bits Array of hard bits with the alleged CRC + * \returns 0 if CRC matches. 1 in case of error. + * + * The crc_bits array must have a length of code->len + */ +int +osmo_crc64gen_check_bits(const struct osmo_crc64gen_code *code, + const ubit_t *in, int len, const ubit_t *crc_bits) +{ + uint64_t crc; + int i; + + crc = osmo_crc64gen_compute_bits(code, in, len); + + for (i=0; ibits; i++) + if (crc_bits[i] ^ ((crc >> (code->bits-i-1)) & 1)) + return 1; + + return 0; +} + + +/*! \brief Computes and writes the CRC value of a given array of bits + * \param[in] code The CRC code description to apply + * \param[in] in Array of hard bits + * \param[in] len Length of the array of hard bits + * \param[in] crc_bits Array of hard bits to write the computed CRC to + * + * The crc_bits array must have a length of code->len + */ +void +osmo_crc64gen_set_bits(const struct osmo_crc64gen_code *code, + const ubit_t *in, int len, ubit_t *crc_bits) +{ + uint64_t crc; + int i; + + crc = osmo_crc64gen_compute_bits(code, in, len); + + for (i=0; ibits; i++) + crc_bits[i] = ((crc >> (code->bits-i-1)) & 1); +} + +/*! @} */ + +/* vim: set syntax=c: */ diff --git a/lib/decoding/osmocom/core/crc64gen.h b/lib/decoding/osmocom/core/crc64gen.h new file mode 100644 index 0000000..aa02e04 --- /dev/null +++ b/lib/decoding/osmocom/core/crc64gen.h @@ -0,0 +1,56 @@ +/* + * crc64gen.h + * + * Copyright (C) 2011 Sylvain Munaut + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#pragma once + +/*! \addtogroup crcgen + * @{ + */ + +/*! \file crc64gen.h + * Osmocom generic CRC routines (for max 64 bits poly) header + */ + + +#include +#include + + +/*! \brief structure describing a given CRC code of max 64 bits */ +struct osmo_crc64gen_code { + int bits; /*!< \brief Actual number of bits of the CRC */ + uint64_t poly; /*!< \brief Polynom (normal representation, MSB omitted */ + uint64_t init; /*!< \brief Initialization value of the CRC state */ + uint64_t remainder; /*!< \brief Remainder of the CRC (final XOR) */ +}; + +uint64_t osmo_crc64gen_compute_bits(const struct osmo_crc64gen_code *code, + const ubit_t *in, int len); +int osmo_crc64gen_check_bits(const struct osmo_crc64gen_code *code, + const ubit_t *in, int len, const ubit_t *crc_bits); +void osmo_crc64gen_set_bits(const struct osmo_crc64gen_code *code, + const ubit_t *in, int len, ubit_t *crc_bits); + + +/*! @} */ + +/* vim: set syntax=c: */ diff --git a/lib/decoding/osmocom/core/crc8gen.c b/lib/decoding/osmocom/core/crc8gen.c new file mode 100644 index 0000000..0b85b0d --- /dev/null +++ b/lib/decoding/osmocom/core/crc8gen.c @@ -0,0 +1,120 @@ +/* + * crc8gen.c + * + * Generic CRC routines (for max 8 bits poly) + * + * Copyright (C) 2011 Sylvain Munaut + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +/*! \addtogroup crcgen + * @{ + */ + +/*! \file crc8gen.c + * Osmocom generic CRC routines (for max 8 bits poly) + */ + +#include + +#include +#include + + +/*! \brief Compute the CRC value of a given array of hard-bits + * \param[in] code The CRC code description to apply + * \param[in] in Array of hard bits + * \param[in] len Length of the array of hard bits + * \returns The CRC value + */ +uint8_t +osmo_crc8gen_compute_bits(const struct osmo_crc8gen_code *code, + const ubit_t *in, int len) +{ + const uint8_t poly = code->poly; + uint8_t crc = code->init; + int i, n = code->bits-1; + + for (i=0; ibits) - 1; + } + + crc ^= code->remainder; + + return crc; +} + + +/*! \brief Checks the CRC value of a given array of hard-bits + * \param[in] code The CRC code description to apply + * \param[in] in Array of hard bits + * \param[in] len Length of the array of hard bits + * \param[in] crc_bits Array of hard bits with the alleged CRC + * \returns 0 if CRC matches. 1 in case of error. + * + * The crc_bits array must have a length of code->len + */ +int +osmo_crc8gen_check_bits(const struct osmo_crc8gen_code *code, + const ubit_t *in, int len, const ubit_t *crc_bits) +{ + uint8_t crc; + int i; + + crc = osmo_crc8gen_compute_bits(code, in, len); + + for (i=0; ibits; i++) + if (crc_bits[i] ^ ((crc >> (code->bits-i-1)) & 1)) + return 1; + + return 0; +} + + +/*! \brief Computes and writes the CRC value of a given array of bits + * \param[in] code The CRC code description to apply + * \param[in] in Array of hard bits + * \param[in] len Length of the array of hard bits + * \param[in] crc_bits Array of hard bits to write the computed CRC to + * + * The crc_bits array must have a length of code->len + */ +void +osmo_crc8gen_set_bits(const struct osmo_crc8gen_code *code, + const ubit_t *in, int len, ubit_t *crc_bits) +{ + uint8_t crc; + int i; + + crc = osmo_crc8gen_compute_bits(code, in, len); + + for (i=0; ibits; i++) + crc_bits[i] = ((crc >> (code->bits-i-1)) & 1); +} + +/*! @} */ + +/* vim: set syntax=c: */ diff --git a/lib/decoding/osmocom/core/crc8gen.h b/lib/decoding/osmocom/core/crc8gen.h new file mode 100644 index 0000000..9513276 --- /dev/null +++ b/lib/decoding/osmocom/core/crc8gen.h @@ -0,0 +1,56 @@ +/* + * crc8gen.h + * + * Copyright (C) 2011 Sylvain Munaut + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#pragma once + +/*! \addtogroup crcgen + * @{ + */ + +/*! \file crc8gen.h + * Osmocom generic CRC routines (for max 8 bits poly) header + */ + + +#include +#include + + +/*! \brief structure describing a given CRC code of max 8 bits */ +struct osmo_crc8gen_code { + int bits; /*!< \brief Actual number of bits of the CRC */ + uint8_t poly; /*!< \brief Polynom (normal representation, MSB omitted */ + uint8_t init; /*!< \brief Initialization value of the CRC state */ + uint8_t remainder; /*!< \brief Remainder of the CRC (final XOR) */ +}; + +uint8_t osmo_crc8gen_compute_bits(const struct osmo_crc8gen_code *code, + const ubit_t *in, int len); +int osmo_crc8gen_check_bits(const struct osmo_crc8gen_code *code, + const ubit_t *in, int len, const ubit_t *crc_bits); +void osmo_crc8gen_set_bits(const struct osmo_crc8gen_code *code, + const ubit_t *in, int len, ubit_t *crc_bits); + + +/*! @} */ + +/* vim: set syntax=c: */ diff --git a/lib/decoding/osmocom/core/crcgen.h b/lib/decoding/osmocom/core/crcgen.h new file mode 100644 index 0000000..7cfe869 --- /dev/null +++ b/lib/decoding/osmocom/core/crcgen.h @@ -0,0 +1,34 @@ +/*! \file crcgen.h + * Osmocom generic CRC routines global header. */ +/* + * Copyright (C) 2011 Sylvain Munaut + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#pragma once + +/*! \defgroup crc Osmocom CRC routines + * @{ + * \file crcgen.h */ + +#include +#include +#include +#include + +/*! @} */ diff --git a/lib/decoding/osmocom/core/defs.h b/lib/decoding/osmocom/core/defs.h new file mode 100644 index 0000000..5e5aa90 --- /dev/null +++ b/lib/decoding/osmocom/core/defs.h @@ -0,0 +1,53 @@ +/*! \file defs.h + * General definitions that are meant to be included from header files. + */ + +#pragma once + +/*! \defgroup utils General-purpose utility functions + * @{ + * \file defs.h */ + +/*! Check for gcc and version. + * + * \note Albeit glibc provides a features.h file that contains a similar + * definition (__GNUC_PREREQ), this definition has been copied from there + * to have it available with other libraries, too. + * + * \return != 0 iff gcc is used and it's version is at least maj.min. + */ +#if defined __GNUC__ && defined __GNUC_MINOR__ +# define OSMO_GNUC_PREREQ(maj, min) \ + ((__GNUC__ << 16) + __GNUC_MINOR__ >= ((maj) << 16) + (min)) +#else +# define OSMO_GNUC_PREREQ(maj, min) 0 +#endif + +/*! Set the deprecated attribute with a message. + */ +#if defined(__clang__) +# define _OSMO_HAS_ATTRIBUTE_DEPRECATED __has_attribute(deprecated) +# define _OSMO_HAS_ATTRIBUTE_DEPRECATED_WITH_MESSAGE __has_extension(attribute_deprecated_with_message) +#elif defined(__GNUC__) +# define _OSMO_HAS_ATTRIBUTE_DEPRECATED 1 +# define _OSMO_HAS_ATTRIBUTE_DEPRECATED_WITH_MESSAGE OSMO_GNUC_PREREQ(4,5) +#endif + +#if _OSMO_HAS_ATTRIBUTE_DEPRECATED_WITH_MESSAGE +# define OSMO_DEPRECATED(text) __attribute__((__deprecated__(text))) +#elif _OSMO_HAS_ATTRIBUTE_DEPRECATED +# define OSMO_DEPRECATED(text) __attribute__((__deprecated__)) +#else +# define OSMO_DEPRECATED(text) +#endif + +#if BUILDING_LIBOSMOCORE +# define OSMO_DEPRECATED_OUTSIDE_LIBOSMOCORE +#else +# define OSMO_DEPRECATED_OUTSIDE_LIBOSMOCORE OSMO_DEPRECATED("For internal use inside libosmocore only.") +#endif + +#undef _OSMO_HAS_ATTRIBUTE_DEPRECATED_WITH_MESSAGE +#undef _OSMO_HAS_ATTRIBUTE_DEPRECATED + +/*! @} */ diff --git a/lib/decoding/osmocom/core/endian.h b/lib/decoding/osmocom/core/endian.h new file mode 100644 index 0000000..6107b12 --- /dev/null +++ b/lib/decoding/osmocom/core/endian.h @@ -0,0 +1,62 @@ +/*! \file endian.h + * + * GNU and FreeBSD have various ways to express the + * endianess but none of them is similiar enough. This + * will create two defines that allows to decide on the + * endian. The following will be defined to either 0 or + * 1 at the end of the file. + * + * OSMO_IS_LITTLE_ENDIAN + * OSMO_IS_BIG_ENDIAN + * + */ + +#pragma once + +#if defined(__FreeBSD__) +#include + #if BYTE_ORDER == LITTLE_ENDIAN + #define OSMO_IS_LITTLE_ENDIAN 1 + #define OSMO_IS_BIG_ENDIAN 0 + #elif BYTE_ORDER == BIG_ENDIAN + #define OSMO_IS_LITTLE_ENDIAN 0 + #define OSMO_IS_BIG_ENDIAN 1 + #else + #error "Unknown endian" + #endif +#elif defined(__APPLE__) +#include + #if defined(__DARWIN_LITTLE_ENDIAN) + #define OSMO_IS_LITTLE_ENDIAN 1 + #define OSMO_IS_BIG_ENDIAN 0 + #elif defined(__DARWIN_BIG_ENDIAN) + #define OSMO_IS_LITTLE_ENDIAN 0 + #define OSMO_IS_BIG_ENDIAN 1 + #else + #error "Unknown endian" + #endif +#elif defined(__linux__) +#include + #if __BYTE_ORDER == __LITTLE_ENDIAN + #define OSMO_IS_LITTLE_ENDIAN 1 + #define OSMO_IS_BIG_ENDIAN 0 + #elif __BYTE_ORDER == __BIG_ENDIAN + #define OSMO_IS_LITTLE_ENDIAN 0 + #define OSMO_IS_BIG_ENDIAN 1 + #else + #error "Unknown endian" + #endif +#else + /* let's try to rely on the compiler. GCC and CLANG/LLVM seem + * to support this ... */ + #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ + #define OSMO_IS_LITTLE_ENDIAN 1 + #define OSMO_IS_BIG_ENDIAN 0 + #elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ + #define OSMO_IS_LITTLE_ENDIAN 0 + #define OSMO_IS_BIG_ENDIAN 1 + #else + #error "Unknown endian" + #endif +#endif + diff --git a/lib/decoding/osmocom/core/linuxlist.h b/lib/decoding/osmocom/core/linuxlist.h new file mode 100644 index 0000000..fee0cc0 --- /dev/null +++ b/lib/decoding/osmocom/core/linuxlist.h @@ -0,0 +1,409 @@ +/*! \file linuxlist.h + * + * Simple doubly linked list implementation. + * + * Some of the internal functions ("__xxx") are useful when + * manipulating whole llists rather than single entries, as + * sometimes we already know the next/prev entries and we can + * generate better code by using them directly rather than + * using the generic single-entry routines. + */ + +#pragma once + +/*! \defgroup linuxlist Simple doubly linked list implementation + * @{ + * \file linuxlist.h */ + +#include + +#if (defined(_WIN16) || defined(_WIN32) || defined(_WIN64)) && !defined(__WINDOWS__) +# define __WINDOWS__ +#endif + +#ifndef inline +# ifndef __WINDOWS__ +# define inline __inline__ +# else +# define inline __inline +# endif +#endif + +static inline void prefetch(const void *x) {;} + +/*! cast a member of a structure out to the containing structure + * + * \param[in] ptr the pointer to the member. + * \param[in] type the type of the container struct this is embedded in. + * \param[in] member the name of the member within the struct. + */ +#define container_of(ptr, type, member) ({ \ + const typeof( ((type *)0)->member ) *__mptr = (ptr); \ + (type *)( (char *)__mptr - offsetof(type, member) );}) + + +/*! + * These are non-NULL pointers that will result in page faults + * under normal circumstances, used to verify that nobody uses + * non-initialized llist entries. + */ +#define LLIST_POISON1 ((void *) 0x00100100) +#define LLIST_POISON2 ((void *) 0x00200200) + +/*! (double) linked list header structure */ +struct llist_head { + /*! Pointer to next and previous item */ + struct llist_head *next, *prev; +}; + +#define LLIST_HEAD_INIT(name) { &(name), &(name) } + +/*! define a statically-initialized \ref llist_head + * \param[in] name Variable name + * + * This is a helper macro that will define a named variable of type + * \ref llist_head and initialize it */ +#define LLIST_HEAD(name) \ + struct llist_head name = LLIST_HEAD_INIT(name) + +/*! initialize a \ref llist_head to point back to self */ +#define INIT_LLIST_HEAD(ptr) do { \ + (ptr)->next = (ptr); (ptr)->prev = (ptr); \ +} while (0) + +/*! Insert a new entry between two known consecutive entries. + * + * This is only for internal llist manipulation where we know + * the prev/next entries already! + */ +static inline void __llist_add(struct llist_head *_new, + struct llist_head *prev, + struct llist_head *next) +{ + next->prev = _new; + _new->next = next; + _new->prev = prev; + prev->next = _new; +} + +/*! add a new entry into a linked list (at head) + * \param _new New entry to be added + * \param head \ref llist_head to add it after + * + * Insert a new entry after the specified head. + * This is good for implementing stacks. + */ +static inline void llist_add(struct llist_head *_new, struct llist_head *head) +{ + __llist_add(_new, head, head->next); +} + +/*! add a new entry into a linked list (at tail) + * \param _new New entry to be added + * \param head Head of linked list to whose tail we shall add \a _new + * + * Insert a new entry before the specified head. + * This is useful for implementing queues. + */ +static inline void llist_add_tail(struct llist_head *_new, struct llist_head *head) +{ + __llist_add(_new, head->prev, head); +} + +/* + * Delete a llist entry by making the prev/next entries + * point to each other. + * + * This is only for internal llist manipulation where we know + * the prev/next entries already! + */ +static inline void __llist_del(struct llist_head * prev, struct llist_head * next) +{ + next->prev = prev; + prev->next = next; +} + +/*! Delete entry from linked list + * \param entry The element to delete from the llist + * + * Note: llist_empty on entry does not return true after this, the entry is + * in an undefined state. + */ +static inline void llist_del(struct llist_head *entry) +{ + __llist_del(entry->prev, entry->next); + entry->next = (struct llist_head *)LLIST_POISON1; + entry->prev = (struct llist_head *)LLIST_POISON2; +} + +/*! Delete entry from linked list and reinitialize it + * \param entry The element to delete from the list + */ +static inline void llist_del_init(struct llist_head *entry) +{ + __llist_del(entry->prev, entry->next); + INIT_LLIST_HEAD(entry); +} + +/*! Delete from one llist and add as another's head + * \param llist The entry to move + * \param head The head that will precede our entry + */ +static inline void llist_move(struct llist_head *llist, struct llist_head *head) +{ + __llist_del(llist->prev, llist->next); + llist_add(llist, head); +} + +/*! Delete from one llist and add as another's tail + * \param llist The entry to move + * \param head The head that will follow our entry + */ +static inline void llist_move_tail(struct llist_head *llist, + struct llist_head *head) +{ + __llist_del(llist->prev, llist->next); + llist_add_tail(llist, head); +} + +/*! Test whether a linked list is empty + * \param[in] head The llist to test. + * \returns 1 if the list is empty, 0 otherwise + */ +static inline int llist_empty(const struct llist_head *head) +{ + return head->next == head; +} + +static inline void __llist_splice(struct llist_head *llist, + struct llist_head *head) +{ + struct llist_head *first = llist->next; + struct llist_head *last = llist->prev; + struct llist_head *at = head->next; + + first->prev = head; + head->next = first; + + last->next = at; + at->prev = last; +} + +/*! Join two llists + * \param llist The new linked list to add + * \param head The place to add \a llist in the other list + */ +static inline void llist_splice(struct llist_head *llist, struct llist_head *head) +{ + if (!llist_empty(llist)) + __llist_splice(llist, head); +} + +/*! join two llists and reinitialise the emptied llist. + * \param llist The new linked list to add. + * \param head The place to add it in the first llist. + * + * The llist at @llist is reinitialised + */ +static inline void llist_splice_init(struct llist_head *llist, + struct llist_head *head) +{ + if (!llist_empty(llist)) { + __llist_splice(llist, head); + INIT_LLIST_HEAD(llist); + } +} + +/*! Get the struct containing this list entry + * \param ptr The \ref llist_head pointer + * \param type The type of the struct this is embedded in + * \param @member The name of the \ref llist_head within the struct + */ +#define llist_entry(ptr, type, member) \ + container_of(ptr, type, member) + +/*! Get the first element from a list + * \param ptr the list head to take the element from. + * \param type the type of the struct this is embedded in. + * \param member the name of the list_head within the struct. + * + * Note, that list is expected to be not empty. + */ +#define llist_first_entry(ptr, type, member) \ + llist_entry((ptr)->next, type, member) + +/*! Get the last element from a list + * \param ptr the list head to take the element from. + * \param type the type of the struct this is embedded in. + * \param member the name of the llist_head within the struct. + * + * Note, that list is expected to be not empty. + */ +#define llist_last_entry(ptr, type, member) \ + llist_entry((ptr)->prev, type, member) + +/*! Get the first element from a list, or NULL + * \param ptr the list head to take the element from. + * \param type the type of the struct this is embedded in. + * \param member the name of the list_head within the struct. + * + * Note that if the list is empty, it returns NULL. + */ +#define llist_first_entry_or_null(ptr, type, member) \ + (!llist_empty(ptr) ? llist_first_entry(ptr, type, member) : NULL) + +/*! Iterate over a linked list + * \param pos The \ref llist_head to use as a loop counter + * \param head The head of the list over which to iterate + */ +#define llist_for_each(pos, head) \ + for (pos = (head)->next, prefetch(pos->next); pos != (head); \ + pos = pos->next, prefetch(pos->next)) + +/*! Iterate over a llist (no prefetch) + * \param pos The \ref llist_head to use as a loop counter + * \param head The head of the list over which to iterate + * + * This variant differs from llist_for_each() in that it's the + * simplest possible llist iteration code, no prefetching is done. + * Use this for code that knows the llist to be very short (empty + * or 1 entry) most of the time. + */ +#define __llist_for_each(pos, head) \ + for (pos = (head)->next; pos != (head); pos = pos->next) + +/*! Iterate over a llist backwards + * \param pos The \ref llist_head to use as a loop counter + * \param head The head of the list over which to iterate + */ +#define llist_for_each_prev(pos, head) \ + for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \ + pos = pos->prev, prefetch(pos->prev)) + +/*! Iterate over a list; safe against removal of llist entry + * \param pos The \ref llist_head to use as a loop counter + * \param n Another \ref llist_head to use as temporary storage + * \param head The head of the list over which to iterate + */ +#define llist_for_each_safe(pos, n, head) \ + for (pos = (head)->next, n = pos->next; pos != (head); \ + pos = n, n = pos->next) + +/*! Iterate over llist of given type + * \param pos The 'type *' to use as a loop counter + * \param head The head of the list over which to iterate + * \param member The name of the \ref llist_head within struct \a pos + */ +#define llist_for_each_entry(pos, head, member) \ + for (pos = llist_entry((head)->next, typeof(*pos), member), \ + prefetch(pos->member.next); \ + &pos->member != (head); \ + pos = llist_entry(pos->member.next, typeof(*pos), member), \ + prefetch(pos->member.next)) + +/*! Iterate backwards over llist of given type. + * \param pos The 'type *' to use as a loop counter + * \param head The head of the list over which to iterate + * \param member The name of the \ref llist_head within struct \a pos + */ +#define llist_for_each_entry_reverse(pos, head, member) \ + for (pos = llist_entry((head)->prev, typeof(*pos), member), \ + prefetch(pos->member.prev); \ + &pos->member != (head); \ + pos = llist_entry(pos->member.prev, typeof(*pos), member), \ + prefetch(pos->member.prev)) + +/*! iterate over llist of given type continuing after existing + * point + * \param pos The 'type *' to use as a loop counter + * \param head The head of the list over which to iterate + * \param member The name of the \ref llist_head within struct \a pos + */ +#define llist_for_each_entry_continue(pos, head, member) \ + for (pos = llist_entry(pos->member.next, typeof(*pos), member), \ + prefetch(pos->member.next); \ + &pos->member != (head); \ + pos = llist_entry(pos->member.next, typeof(*pos), member), \ + prefetch(pos->member.next)) + +/*! iterate over llist of given type, safe against removal of + * non-consecutive(!) llist entries + * \param pos The 'type *' to use as a loop counter + * \param n Another type * to use as temporary storage + * \param head The head of the list over which to iterate + * \param member The name of the \ref llist_head within struct \a pos + */ +#define llist_for_each_entry_safe(pos, n, head, member) \ + for (pos = llist_entry((head)->next, typeof(*pos), member), \ + n = llist_entry(pos->member.next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = n, n = llist_entry(n->member.next, typeof(*n), member)) + +/** + * llist_for_each_rcu - iterate over an rcu-protected llist + * @pos: the &struct llist_head to use as a loop counter. + * @head: the head for your llist. + */ +#define llist_for_each_rcu(pos, head) \ + for (pos = (head)->next, prefetch(pos->next); pos != (head); \ + pos = pos->next, ({ smp_read_barrier_depends(); 0;}), prefetch(pos->next)) + +#define __llist_for_each_rcu(pos, head) \ + for (pos = (head)->next; pos != (head); \ + pos = pos->next, ({ smp_read_barrier_depends(); 0;})) + +/** + * llist_for_each_safe_rcu - iterate over an rcu-protected llist safe + * against removal of llist entry + * @pos: the &struct llist_head to use as a loop counter. + * @n: another &struct llist_head to use as temporary storage + * @head: the head for your llist. + */ +#define llist_for_each_safe_rcu(pos, n, head) \ + for (pos = (head)->next, n = pos->next; pos != (head); \ + pos = n, ({ smp_read_barrier_depends(); 0;}), n = pos->next) + +/** + * llist_for_each_entry_rcu - iterate over rcu llist of given type + * @pos: the type * to use as a loop counter. + * @head: the head for your llist. + * @member: the name of the llist_struct within the struct. + */ +#define llist_for_each_entry_rcu(pos, head, member) \ + for (pos = llist_entry((head)->next, typeof(*pos), member), \ + prefetch(pos->member.next); \ + &pos->member != (head); \ + pos = llist_entry(pos->member.next, typeof(*pos), member), \ + ({ smp_read_barrier_depends(); 0;}), \ + prefetch(pos->member.next)) + + +/** + * llist_for_each_continue_rcu - iterate over an rcu-protected llist + * continuing after existing point. + * @pos: the &struct llist_head to use as a loop counter. + * @head: the head for your llist. + */ +#define llist_for_each_continue_rcu(pos, head) \ + for ((pos) = (pos)->next, prefetch((pos)->next); (pos) != (head); \ + (pos) = (pos)->next, ({ smp_read_barrier_depends(); 0;}), prefetch((pos)->next)) + +/*! count nr of llist items by iterating. + * \param head The llist head to count items of. + * \returns Number of items. + * + * This function is not efficient, mostly useful for small lists and non time + * critical cases like unit tests. + */ +static inline unsigned int llist_count(struct llist_head *head) +{ + struct llist_head *entry; + unsigned int i = 0; + llist_for_each(entry, head) + i++; + return i; +} + +/*! + * @} + */ diff --git a/lib/decoding/osmocom/core/panic.c b/lib/decoding/osmocom/core/panic.c new file mode 100644 index 0000000..d545a60 --- /dev/null +++ b/lib/decoding/osmocom/core/panic.c @@ -0,0 +1,100 @@ +/*! \file panic.c + * Routines for panic handling. */ +/* + * (C) 2010 by Sylvain Munaut + * + * All Rights Reserved + * + * SPDX-License-Identifier: GPL-2.0+ + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * + */ + +/*! \addtogroup utils + * @{ + * \file panic.c */ + +#include +//#include + +//#include "../config.h" + + +static osmo_panic_handler_t osmo_panic_handler = (void*)0; + + +#ifndef PANIC_INFLOOP + +#include +#include + +static void osmo_panic_default(const char *fmt, va_list args) +{ + vfprintf(stderr, fmt, args); + //osmo_generate_backtrace(); + abort(); +} + +#else + +static void osmo_panic_default(const char *fmt, va_list args) +{ + while (1); +} + +#endif + + +/*! Terminate the current program with a panic + * + * You can call this function in case some severely unexpected situation + * is detected and the program is supposed to terminate in a way that + * reports the fact that it terminates. + * + * The application can register a panic handler function using \ref + * osmo_set_panic_handler. If it doesn't, a default panic handler + * function is called automatically. + * + * The default function on most systems will generate a backtrace and + * then abort() the process. + */ +void osmo_panic(const char *fmt, ...) +{ + va_list args; + + va_start(args, fmt); + + if (osmo_panic_handler) + osmo_panic_handler(fmt, args); + else + osmo_panic_default(fmt, args); + + va_end(args); +} + + +/*! Set the panic handler + * \param[in] h New panic handler function + * + * This changes the panic handling function from the currently active + * function to a new call-back function supplied by the caller. + */ +void osmo_set_panic_handler(osmo_panic_handler_t h) +{ + osmo_panic_handler = h; +} + +/*! @} */ diff --git a/lib/decoding/osmocom/core/panic.h b/lib/decoding/osmocom/core/panic.h new file mode 100644 index 0000000..2bb4240 --- /dev/null +++ b/lib/decoding/osmocom/core/panic.h @@ -0,0 +1,15 @@ +#pragma once + +/*! \addtogroup utils + * @{ + * \file panic.h */ + +#include + +/*! panic handler callback function type */ +typedef void (*osmo_panic_handler_t)(const char *fmt, va_list args); + +extern void osmo_panic(const char *fmt, ...); +extern void osmo_set_panic_handler(osmo_panic_handler_t h); + +/*! @} */ diff --git a/lib/decoding/osmocom/core/utils.h b/lib/decoding/osmocom/core/utils.h new file mode 100644 index 0000000..54c8216 --- /dev/null +++ b/lib/decoding/osmocom/core/utils.h @@ -0,0 +1,129 @@ +#pragma once + +#include + +//#include +//#include + +/*! \defgroup utils General-purpose utility functions + * @{ + * \file utils.h */ + +/*! Determine number of elements in an array of static size */ +#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) +/*! Return the maximum of two specified values */ +#define OSMO_MAX(a, b) ((a) >= (b) ? (a) : (b)) +/*! Return the minimum of two specified values */ +#define OSMO_MIN(a, b) ((a) >= (b) ? (b) : (a)) +/*! Stringify the name of a macro x, e.g. an FSM event name. + * Note: if nested within another preprocessor macro, this will + * stringify the value of x instead of its name. */ +#define OSMO_STRINGIFY(x) #x +/*! Stringify the value of a macro x, e.g. a port number. */ +#define OSMO_STRINGIFY_VAL(x) OSMO_STRINGIFY(x) +/*! Make a value_string entry from an enum value name */ +#define OSMO_VALUE_STRING(x) { x, #x } +/*! Number of bytes necessary to store given BITS */ +#define OSMO_BYTES_FOR_BITS(BITS) ((BITS + 8 - 1) / 8) + +#include +#include +#include + +#define __attribute__(_arg_) +#define __deprecated__ + +/*! A mapping between human-readable string and numeric value */ +struct value_string { + unsigned int value; /*!< numeric value */ + const char *str; /*!< human-readable string */ +}; + +//const char *get_value_string(const struct value_string *vs, uint32_t val); +const char *get_value_string_or_null(const struct value_string *vs, + uint32_t val); + +int get_string_value(const struct value_string *vs, const char *str); + +char osmo_bcd2char(uint8_t bcd); +/* only works for numbers in ascci */ +uint8_t osmo_char2bcd(char c); + +int osmo_hexparse(const char *str, uint8_t *b, int max_len); + +char *osmo_ubit_dump(const uint8_t *bits, unsigned int len); +char *osmo_hexdump(const unsigned char *buf, int len); +char *osmo_hexdump_nospc(const unsigned char *buf, int len); +char *osmo_osmo_hexdump_nospc(const unsigned char *buf, int len) __attribute__((__deprecated__)); + +#define osmo_static_assert(exp, name) typedef int dummy##name [(exp) ? 1 : -1] __attribute__((__unused__)); + +void osmo_str2lower(char *out, const char *in); +void osmo_str2upper(char *out, const char *in); + +#define OSMO_SNPRINTF_RET(ret, rem, offset, len) \ +do { \ + len += ret; \ + if (ret > rem) \ + ret = rem; \ + offset += ret; \ + rem -= ret; \ +} while (0) + +/*! Helper macro to terminate when an assertion failes + * \param[in] exp Predicate to verify + * This function will generate a backtrace and terminate the program if + * the predicate evaluates to false (0). + */ +#define OSMO_ASSERT(exp) \ + if (!(exp)) { \ + fprintf(stderr, "Assert failed %s %s:%d\n", #exp, __BASE_FILE__, __LINE__); \ + /*osmo_generate_backtrace(); \ */\ + abort(); \ + } + +/*! duplicate a string using talloc and release its prior content (if any) + * \param[in] ctx Talloc context to use for allocation + * \param[out] dst pointer to string, will be updated with ptr to new string + * \param[in] newstr String that will be copieed to newly allocated string */ +/*static inline void osmo_talloc_replace_string(void *ctx, char **dst, const char *newstr)*/ +/*{*/ +/* if (*dst)*/ +/* talloc_free(*dst);*/ +/* *dst = talloc_strdup(ctx, newstr);*/ +/*}*/ + +/*! Append to a string and re-/allocate if necessary. + * \param[in] ctx Talloc context to use for initial allocation. + * \param[in,out] dest char* to re-/allocate and append to. + * \param[in] fmt printf-like string format. + * \param[in] args Arguments for fmt. + * + * \a dest may be passed in NULL, or a string previously allocated by talloc. + * If an existing string is passed in, it will remain associated with whichever + * ctx it was allocated before, regardless whether it matches \a ctx or not. + */ +/*#define osmo_talloc_asprintf(ctx, dest, fmt, args ...) \*/ +/* do { \*/ +/* if (!dest) \*/ +/* dest = talloc_asprintf(ctx, fmt, ## args); \*/ +/* else \*/ +/* dest = talloc_asprintf_append((char*)dest, fmt, ## args); \*/ +/* } while (0)*/ + +int osmo_constant_time_cmp(const uint8_t *exp, const uint8_t *rel, const int count); +uint64_t osmo_decode_big_endian(const uint8_t *data, size_t data_len); +uint8_t *osmo_encode_big_endian(uint64_t value, size_t data_len); + +size_t osmo_strlcpy(char *dst, const char *src, size_t siz); + +bool osmo_is_hexstr(const char *str, int min_digits, int max_digits, + bool require_even); + +bool osmo_identifier_valid(const char *str); +bool osmo_separated_identifiers_valid(const char *str, const char *sep_chars); + +const char *osmo_escape_str(const char *str, int len); +const char *osmo_escape_str_buf(const char *str, int in_len, char *buf, size_t bufsize); + +/*! @} */ -- cgit v1.2.3