--- .gitignore | 3 +- include/Makefile.am | 6 + include/osmocom/core/bitXXgen.h.tpl | 86 ++++++++++++++ include/osmocom/core/bits.h | 45 +++++++- include/osmocom/core/msgb.h | 23 ++-- tests/bits/bitrev_test.c | 218 +++++++++++++++++++++++++++++++++++- tests/bits/bitrev_test.ok | 31 +++++ 7 files changed, 399 insertions(+), 13 deletions(-) create mode 100644 include/osmocom/core/bitXXgen.h.tpl diff --git a/.gitignore b/.gitignore index 71b27f2..3fa1bbc 100644 --- a/.gitignore +++ b/.gitignore @@ -55,6 +55,7 @@ tests/testsuite tests/testsuite.dir/ tests/testsuite.log +tests/utils/utils_test tests/sms/sms_test tests/timer/timer_test tests/msgfile/msgfile_test @@ -89,7 +90,7 @@ doc/html.tar src/crc*gen.c include/osmocom/core/crc*gen.h - +include/osmocom/core/bit*gen.h # vi files *.sw? diff --git a/include/Makefile.am b/include/Makefile.am index b035906..18011ff 100644 --- a/include/Makefile.am +++ b/include/Makefile.am @@ -2,6 +2,8 @@ nobase_include_HEADERS = \ osmocom/codec/codec.h \ osmocom/core/application.h \ osmocom/core/backtrace.h \ + osmocom/core/bit32gen.h \ + osmocom/core/bit64gen.h \ osmocom/core/bits.h \ osmocom/core/bitvec.h \ osmocom/core/conv.h \ @@ -107,6 +109,10 @@ endif noinst_HEADERS = osmocom/core/timer_compat.h +osmocom/core/bit%gen.h: osmocom/core/bitXXgen.h.tpl + $(AM_V_GEN)$(MKDIR_P) $(dir $@) + $(AM_V_GEN)sed -e's/XX/$*/g' $< > $@ + osmocom/core/crc%gen.h: osmocom/core/crcXXgen.h.tpl $(AM_V_GEN)$(MKDIR_P) $(dir $@) $(AM_V_GEN)sed -e's/XX/$*/g' $< > $@ diff --git a/include/osmocom/core/bitXXgen.h.tpl b/include/osmocom/core/bitXXgen.h.tpl new file mode 100644 index 0000000..1deffb9 --- /dev/null +++ b/include/osmocom/core/bitXXgen.h.tpl @@ -0,0 +1,86 @@ +/* + * bitXXgen.h + * + * Copyright (C) 2014 Max <max.suraev@fairwaves.ru> + * + * 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. + */ + + +/* Load unaligned n-byte integer (little-endian encoding) into uintXX_t */ +static inline uintXX_t osmo_loadXXle_ext(const uint8_t *p, uint8_t n) +{ + uint8_t i; + uintXX_t r = 0; + for(i = 0; i < n; r |= ((uintXX_t)p[i] << (8 * i)), i++); + return r; +} + +/* Load unaligned n-byte integer (big-endian encoding) into uintXX_t */ +static inline uintXX_t osmo_loadXXbe_ext(const uint8_t *p, uint8_t n) +{ + uint8_t i; + uintXX_t r = 0; + for(i = 0; i < n; r |= ((uintXX_t)p[i] << (XX - 8* (1 + i))), i++); + return r; +} + + +/* Store unaligned n-byte integer (little-endian encoding) into uintXX_t */ +static inline void osmo_storeXXle_ext(uintXX_t x, uint8_t *p, uint8_t n) +{ + uint8_t i; + for(i = 0; i < n; p[i] = (x >> i * 8) & 0xFF, i++); +} + +/* Store unaligned n-byte integer (big-endian encoding) into uintXX_t */ +static inline void osmo_storeXXbe_ext(uintXX_t x, uint8_t *p, uint8_t n) +{ + uint8_t i; + for(i = 0; i < n; p[i] = (x >> ((n - 1 - i) * 8)) & 0xFF, i++); +} + + +/* Convenience function for most-used cases */ + + +/* Load unaligned XX-bit integer (little-endian encoding) */ +static inline uintXX_t osmo_loadXXle(const uint8_t *p) +{ + return osmo_loadXXle_ext(p, XX / 8); +} + +/* Load unaligned XX-bit integer (big-endian encoding) */ +static inline uintXX_t osmo_loadXXbe(const uint8_t *p) +{ + return osmo_loadXXbe_ext(p, XX / 8); +} + + +/* Store unaligned XX-bit integer (little-endian encoding) */ +static inline void osmo_storeXXle(uintXX_t x, uint8_t *p) +{ + return osmo_storeXXle_ext(x, p, XX / 8); +} + +/* Store unaligned XX-bit integer (big-endian encoding) */ +static inline void osmo_storeXXbe(uintXX_t x, uint8_t *p) +{ + return osmo_storeXXbe_ext(x, p, XX / 8); +} + + diff --git a/include/osmocom/core/bits.h b/include/osmocom/core/bits.h index 4c68532..09d163d 100644 --- a/include/osmocom/core/bits.h +++ b/include/osmocom/core/bits.h @@ -2,7 +2,9 @@ #define _OSMO_BITS_H #include <stdint.h> - +#include <stddef.h> +#include <osmocom/core/bit32gen.h> +#include <osmocom/core/bit64gen.h> /*! \defgroup bits soft, unpacked and packed bits * @{ */ @@ -15,6 +17,37 @@ typedef int8_t sbit_t; /*!< \brief soft bit (-127...127) */ typedef uint8_t ubit_t; /*!< \brief unpacked bit (0 or 1) */ typedef uint8_t pbit_t; /*!< \brief packed bis (8 bits in a byte) */ +/* Load unaligned 16-bit integer (little-endian encoding) */ +static inline uint16_t osmo_load16le(const uint8_t *p) +{ + return p[0] | (p[1] << 8); +} + +/* Load unaligned 16-bit integer (big-endian encoding) */ +static inline uint16_t osmo_load16be(const uint8_t *p) +{ + return (p[0] << 8) | p[1]; +} + +/* Store unaligned 16-bit integer (little-endian encoding) */ +static inline void osmo_store16le(uint16_t a, uint8_t *p) +{ + p[0] = a & 0xFF; + p[1] = (a >> 8) & 0xFF; +} + +/* Store unaligned 16-bit integer (big-endian encoding) */ +static inline void osmo_store16be(uint16_t a, uint8_t *p) +{ + p[0] = (a >> 8) & 0xFF; + p[1] = a & 0xFF; +} + +/* + Less trivial LE/BE functions (24 bits and above) are autogenerated + see included bitXXgen.h files +*/ + /* NOTE on the endianess of pbit_t: Bits in a pbit_t are ordered MSB first, i.e. 0x80 is the first bit. @@ -73,6 +106,16 @@ uint32_t osmo_revbytebits_8(uint8_t x); /* \brief reverse the bits of each byte in a given buffer */ void osmo_revbytebits_buf(uint8_t *buf, int len); +/* \brief reverse the order of the bytes in a given buffer */ +void osmo_revbytes_buf(uint8_t *buf, size_t len); + +/* \brief left circular shift */ +static inline uint16_t rol16(uint16_t in, unsigned shift) +{ + return (in << shift) | (in >> (16 - shift)); +} + + /*! @} */ #endif /* _OSMO_BITS_H */ diff --git a/include/osmocom/core/msgb.h b/include/osmocom/core/msgb.h index fe2733b..72fdc24 100644 --- a/include/osmocom/core/msgb.h +++ b/include/osmocom/core/msgb.h @@ -23,6 +23,7 @@ #include <stdint.h> #include <osmocom/core/linuxlist.h> #include <osmocom/core/utils.h> +#include <osmocom/core/bits.h> /*! \defgroup msgb Message buffers * @{ @@ -204,8 +205,7 @@ static inline void msgb_put_u8(struct msgb *msgb, uint8_t word) static inline void msgb_put_u16(struct msgb *msgb, uint16_t word) { uint8_t *space = msgb_put(msgb, 2); - space[0] = word >> 8 & 0xFF; - space[1] = word & 0xFF; + osmo_store16be(word, space); } /*! \brief append a uint32 value to the end of the message @@ -215,10 +215,7 @@ static inline void msgb_put_u16(struct msgb *msgb, uint16_t word) static inline void msgb_put_u32(struct msgb *msgb, uint32_t word) { uint8_t *space = msgb_put(msgb, 4); - space[0] = word >> 24 & 0xFF; - space[1] = word >> 16 & 0xFF; - space[2] = word >> 8 & 0xFF; - space[3] = word & 0xFF; + osmo_store32be(word, space); } /*! \brief remove data from end of message @@ -235,6 +232,7 @@ static inline unsigned char *msgb_get(struct msgb *msgb, unsigned int len) msgb->len -= len; return tmp; } + /*! \brief remove uint8 from end of message * \param[in] msgb message buffer * \returns 8bit value taken from end of msgb @@ -244,6 +242,7 @@ static inline uint8_t msgb_get_u8(struct msgb *msgb) uint8_t *space = msgb_get(msgb, 1); return space[0]; } + /*! \brief remove uint16 from end of message * \param[in] msgb message buffer * \returns 16bit value taken from end of msgb @@ -251,8 +250,9 @@ static inline uint8_t msgb_get_u8(struct msgb *msgb) static inline uint16_t msgb_get_u16(struct msgb *msgb) { uint8_t *space = msgb_get(msgb, 2); - return space[0] << 8 | space[1]; + return osmo_load16be(space); } + /*! \brief remove uint32 from end of message * \param[in] msgb message buffer * \returns 32bit value taken from end of msgb @@ -260,7 +260,7 @@ static inline uint16_t msgb_get_u16(struct msgb *msgb) static inline uint32_t msgb_get_u32(struct msgb *msgb) { uint8_t *space = msgb_get(msgb, 4); - return space[0] << 24 | space[1] << 16 | space[2] << 8 | space[3]; + return osmo_load32be(space); } /*! \brief prepend (push) some data to start of message @@ -284,6 +284,7 @@ static inline unsigned char *msgb_push(struct msgb *msgb, unsigned int len) msgb->len += len; return msgb->data; } + /*! \brief remove (pull) a header from the front of the message buffer * \param[in] msgb message buffer * \param[in] len number of octets to be pulled @@ -308,6 +309,7 @@ static inline uint8_t msgb_pull_u8(struct msgb *msgb) uint8_t *space = msgb_pull(msgb, 1) - 1; return space[0]; } + /*! \brief remove uint16 from front of message * \param[in] msgb message buffer * \returns 16bit value taken from end of msgb @@ -315,8 +317,9 @@ static inline uint8_t msgb_pull_u8(struct msgb *msgb) static inline uint16_t msgb_pull_u16(struct msgb *msgb) { uint8_t *space = msgb_pull(msgb, 2) - 2; - return space[0] << 8 | space[1]; + return osmo_load16be(space); } + /*! \brief remove uint32 from front of message * \param[in] msgb message buffer * \returns 32bit value taken from end of msgb @@ -324,7 +327,7 @@ static inline uint16_t msgb_pull_u16(struct msgb *msgb) static inline uint32_t msgb_pull_u32(struct msgb *msgb) { uint8_t *space = msgb_pull(msgb, 4) - 4; - return space[0] << 24 | space[1] << 16 | space[2] << 8 | space[3]; + return osmo_load32be(space); } /*! \brief Increase headroom of empty msgb, reducing the tailroom diff --git a/tests/bits/bitrev_test.c b/tests/bits/bitrev_test.c index 5eca990..fc5a811 100644 --- a/tests/bits/bitrev_test.c +++ b/tests/bits/bitrev_test.c @@ -1,20 +1,192 @@ - +#include <inttypes.h> #include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <string.h> +#include <time.h> +#include <stdbool.h> #include <osmocom/core/utils.h> #include <osmocom/core/bits.h> static const uint8_t input[] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 }; static const uint8_t exp_out[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 }; +static char s[18]; + +enum END {LE, BE}; + +const char * end2str(enum END e) { + if (e == LE) return "LE"; + return "BE"; +} + + +/* convenience wrappers */ + +inline uint64_t load64(enum END e, const uint8_t *buf, unsigned nbytes) { + return (e == BE) ? osmo_load64be_ext(buf, nbytes) : osmo_load64le_ext(buf, nbytes); +} + +inline uint32_t load32(enum END e, const uint8_t *buf, unsigned nbytes) { + return (e == BE) ? osmo_load32be_ext(buf, nbytes) : osmo_load32le_ext(buf, nbytes); +} + +inline uint16_t load16(enum END e, const uint8_t *buf) { + return (e == BE) ? osmo_load16be(buf) : osmo_load16le(buf); +} + +inline void store64(enum END e, uint64_t t, uint8_t *buf, unsigned nbytes) { + (e == BE) ? osmo_store64be_ext(t, buf, nbytes) : osmo_store64le_ext(t, buf, nbytes); +} + +inline void store32(enum END e, uint64_t t, uint8_t *buf, unsigned nbytes) { + (e == BE) ? osmo_store32be_ext(t, buf, nbytes) : osmo_store32le_ext(t, buf, nbytes); +} + +inline void store16(enum END e, uint64_t t, uint8_t *buf) { + (e == BE) ? osmo_store16be(t, buf) : osmo_store16le(t, buf); +} + + +/* helper functions */ + +inline bool printcheck(bool chk, unsigned nbytes, enum END e, bool b) +{ + if (!chk) { + printf("%u %s FAILED", nbytes * 8, end2str(e)); + return true; + } + printf("%u %s OK", nbytes * 8, end2str(e)); + return b; +} + +inline bool dumpcheck(const char *dump, const char *s, unsigned nbytes, bool chk, enum END e, bool b) +{ + bool x = printcheck(chk, nbytes, e, b); + if (!dump) return x; + + int m = memcmp(s, dump, nbytes); + if (0 == m) { + printf(", storage OK"); + return x; + } + printf(", [%d]", m); + + return true; +} + + +/* printcheckXX(): load/store 'test' and check against 'expected' value, compare to 'dump' buffer if given and print if necessary */ + +inline void printcheck64(enum END e, unsigned nbytes, uint64_t test, uint64_t expected, const char *dump, bool print) +{ + uint8_t buf[nbytes]; + + store64(e, test, buf, nbytes); + + char *s = osmo_hexdump_nospc(buf, nbytes); + uint64_t result = load64(e, buf, nbytes); + + print = dumpcheck(dump, s, nbytes, result == expected, e, print); + + if (print) + printf(": buffer %s known buffer %s loaded %.16" PRIx64 " expected %.16" PRIx64, s, dump, result, expected); + printf("\n"); +} + +inline void printcheck32(enum END e, unsigned nbytes, uint32_t test, uint32_t expected, const char *dump, bool print) +{ + uint8_t buf[nbytes]; + + store32(e, test, buf, nbytes); + + char *s = osmo_hexdump_nospc(buf, nbytes); + uint32_t result = load32(e, buf, nbytes); + + print = dumpcheck(dump, s, nbytes, result == expected, e, print); + + if (print) + printf(": buffer %s known buffer %s loaded %.8" PRIx32 " expected %.8" PRIx32, s, dump, result, expected); + printf("\n"); +} + +inline void printcheck16(enum END e, uint32_t test, uint32_t expected, const char *dump, bool print) +{ + uint8_t buf[2]; + + store16(e, test, buf); + + char *s = osmo_hexdump_nospc(buf, 2); + uint16_t result = load16(e, buf); + + print = dumpcheck(dump, s, 2, result == expected, e, print); + + if (print) + printf(": buffer %s known buffer %s loaded %.4" PRIx16 " expected %.4" PRIx16, s, dump, result, expected); + printf("\n"); +} + + +/* compute expected value - zero excessive bytes */ + +inline uint64_t exp64(enum END e, unsigned nbytes, uint64_t value) { + uint8_t adj = 64 - nbytes * 8; + uint64_t v = value << adj; + return (e == LE) ? v >> adj : v; +} + +inline uint32_t exp32(enum END e, unsigned nbytes, uint32_t value) { + uint8_t adj = 32 - nbytes * 8; + uint32_t v = value << adj; + return (e == LE) ? v >> adj : v; +} + + +/* run actual tests - if 'test' is 0 than generate random test value internally */ + +inline void check64(uint64_t test, uint64_t expected, unsigned nbytes, enum END e) +{ + bool print = true; + if (0 == test && 0 == expected) { + test = ((uint64_t)rand() << 32) + rand(); + expected = exp64(e, nbytes, test); + print = false; + } + snprintf(s, 17, "%.16" PRIx64, expected); + printcheck64(e, nbytes, test, expected, (BE == e) ? s : NULL, print); +} + +inline void check32(uint32_t test, uint32_t expected, unsigned nbytes, enum END e) +{ + bool print = true; + if (0 == test && 0 == expected) { + test = rand(); + expected = exp32(e, nbytes, test); + print = false; + } + snprintf(s, 17, "%.8" PRIx32, expected); + printcheck32(e, nbytes, test, expected, (BE == e) ? s : NULL, print); +} + +inline void check16(uint16_t test, enum END e) +{ + bool print = true; + if (0 == test) { + test = (uint16_t)rand(); + print = false; + } + snprintf(s, 17, "%.4" PRIx16, test); + printcheck16(e, test, test, (BE == e) ? s : NULL, print); +} + int main(int argc, char **argv) { uint8_t out[ARRAY_SIZE(input)]; unsigned int offs; + srand(time(NULL)); + for (offs = 0; offs < sizeof(out); offs++) { uint8_t *start = out + offs; uint8_t len = sizeof(out) - offs; @@ -32,5 +204,49 @@ int main(int argc, char **argv) printf("\n"); } + printf("checking byte packing...\n"); + + printf("running static tests...\n"); + + check64(0xDEADBEEFF00DCAFE, 0xDEADBEEFF00DCAFE, 8, BE); + check64(0xDEADBEEFF00DCAFE, 0xADBEEFF00DCAFE00, 7, BE); + check64(0xDEADBEEFF00DCAFE, 0xBEEFF00DCAFE0000, 6, BE); + check64(0xDEADBEEFF00DCAFE, 0xEFF00DCAFE000000, 5, BE); + + check64(0xDEADBEEFF00DCAFE, 0xDEADBEEFF00DCAFE, 8, LE); + check64(0xDEADBEEFF00DCAFE, 0x00ADBEEFF00DCAFE, 7, LE); + check64(0xDEADBEEFF00DCAFE, 0x0000BEEFF00DCAFE, 6, LE); + check64(0xDEADBEEFF00DCAFE, 0x000000EFF00DCAFE, 5, LE); + + check32(0xBABEFACE, 0xBABEFACE, 4, BE); + check32(0xBABEFACE, 0xBEFACE00, 3, BE); + + check32(0xBABEFACE, 0xBABEFACE, 4, LE); + check32(0xBABEFACE, 0x00BEFACE, 3, LE); + + check16(0xB00B, BE); + check16(0xB00B, LE); + + printf("running random tests...\n"); + + check64(0, 0, 8, BE); + check64(0, 0, 7, BE); + check64(0, 0, 6, BE); + check64(0, 0, 5, BE); + + check64(0, 0, 8, LE); + check64(0, 0, 7, LE); + check64(0, 0, 6, LE); + check64(0, 0, 5, LE); + + check32(0, 0, 4, BE); + check32(0, 0, 3, BE); + + check32(0, 0, 4, LE); + check32(0, 0, 3, LE); + + check16(0, BE); + check16(0, LE); + return 0; } diff --git a/tests/bits/bitrev_test.ok b/tests/bits/bitrev_test.ok index 47f402f..90cb295 100644 --- a/tests/bits/bitrev_test.ok +++ b/tests/bits/bitrev_test.ok @@ -22,3 +22,34 @@ REVERSED: 02 01 INORDER: 80 REVERSED: 01 +checking byte packing... +running static tests... +64 BE OK, storage OK: buffer deadbeeff00dcafe known buffer deadbeeff00dcafe loaded deadbeeff00dcafe expected deadbeeff00dcafe +56 BE OK, storage OK: buffer adbeeff00dcafe known buffer adbeeff00dcafe00 loaded adbeeff00dcafe00 expected adbeeff00dcafe00 +48 BE OK, storage OK: buffer beeff00dcafe known buffer beeff00dcafe0000 loaded beeff00dcafe0000 expected beeff00dcafe0000 +40 BE OK, storage OK: buffer eff00dcafe known buffer eff00dcafe000000 loaded eff00dcafe000000 expected eff00dcafe000000 +64 LE OK: buffer feca0df0efbeadde known buffer (null) loaded deadbeeff00dcafe expected deadbeeff00dcafe +56 LE OK: buffer feca0df0efbead known buffer (null) loaded 00adbeeff00dcafe expected 00adbeeff00dcafe +48 LE OK: buffer feca0df0efbe known buffer (null) loaded 0000beeff00dcafe expected 0000beeff00dcafe +40 LE OK: buffer feca0df0ef known buffer (null) loaded 000000eff00dcafe expected 000000eff00dcafe +32 BE OK, storage OK: buffer babeface known buffer babeface loaded babeface expected babeface +24 BE OK, storage OK: buffer beface known buffer beface00 loaded beface00 expected beface00 +32 LE OK: buffer cefabeba known buffer (null) loaded babeface expected babeface +24 LE OK: buffer cefabe known buffer (null) loaded 00beface expected 00beface +16 BE OK, storage OK: buffer b00b known buffer b00b loaded b00b expected b00b +16 LE OK: buffer 0bb0 known buffer (null) loaded b00b expected b00b +running random tests... +64 BE OK, storage OK +56 BE OK, storage OK +48 BE OK, storage OK +40 BE OK, storage OK +64 LE OK +56 LE OK +48 LE OK +40 LE OK +32 BE OK, storage OK +24 BE OK, storage OK +32 LE OK +24 LE OK +16 BE OK, storage OK +16 LE OK -- 1.8.3.2 --------------070304090402030003020005 Content-Type: text/x-patch; name="0002-Add-Kasumi-cipher-implementation.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0002-Add-Kasumi-cipher-implementation.patch"