From 64f6b534afd44bdf40d647331465bb386164f73a Mon Sep 17 00:00:00 2001 From: Pekka Riikonen Date: Sun, 16 Dec 2007 14:20:13 +0000 Subject: [PATCH] Added SILC Bit Operations API. --- CHANGES.RUNTIME | 4 + lib/silcutil/Makefile.ad | 7 +- lib/silcutil/silcbitops.c | 191 +++++++++++++++++++ lib/silcutil/silcbitops.h | 274 +++++++++++++++++++++++++++ lib/silcutil/tests/Makefile.am | 3 +- lib/silcutil/tests/test_silcbitops.c | 137 ++++++++++++++ 6 files changed, 613 insertions(+), 3 deletions(-) create mode 100644 lib/silcutil/silcbitops.c create mode 100644 lib/silcutil/silcbitops.h create mode 100644 lib/silcutil/tests/test_silcbitops.c diff --git a/CHANGES.RUNTIME b/CHANGES.RUNTIME index 119de24d..f333c3e1 100644 --- a/CHANGES.RUNTIME +++ b/CHANGES.RUNTIME @@ -1,3 +1,7 @@ +Sun Dec 16 16:18:04 EET 2007 Pekka Riikonen + + * Added SILC Bit Operations API to lib/silcutil/silcbitops.[ch]. + Sat Dec 15 19:59:53 EET 2007 Pekka Riikonen * Added SILC Tls API for Thread-local storage in diff --git a/lib/silcutil/Makefile.ad b/lib/silcutil/Makefile.ad index 09bc5bcd..f15910f5 100644 --- a/lib/silcutil/Makefile.ad +++ b/lib/silcutil/Makefile.ad @@ -73,7 +73,8 @@ libsilcutil_la_SOURCES = \ silcthread.c \ silcdll.c \ silcenv.c \ - silcbase64.c + silcbase64.c \ + silcbitops.c #ifdef SILC_DIST_TOOLKIT include_HEADERS = \ @@ -93,6 +94,7 @@ include_HEADERS = \ silcschedule.h \ silcschedule_i.h \ silcthread.h \ + silcthread_i.h \ silclist.h \ silcdlist.h \ silcfileutil.h \ @@ -119,7 +121,8 @@ include_HEADERS = \ silcsnprintf.h \ silcdll.h \ silcenv.h \ - silcbase64.h + silcbase64.h \ + silcbitops.h SILC_EXTRA_DIST = tests #endif SILC_DIST_TOOLKIT diff --git a/lib/silcutil/silcbitops.c b/lib/silcutil/silcbitops.c new file mode 100644 index 00000000..4eeca575 --- /dev/null +++ b/lib/silcutil/silcbitops.c @@ -0,0 +1,191 @@ +/* + + silcbitops.c + + Author: Pekka Riikonen + + Copyright (C) 2007 Pekka Riikonen + + 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; version 2 of the License. + + 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. + +*/ + +#include "silc.h" + +#define SILC_BIT_POS(bit) (bit / SILC_BIT_SIZE) +#define SILC_BIT_MASK(bit) (1UL << (bit % SILC_BIT_SIZE)) + +/* Set bit */ + +SilcBool silc_bit_set(volatile unsigned long *bitmap, SilcUInt32 bitmap_size, + SilcUInt32 bit) +{ + SilcUInt32 pos = SILC_BIT_POS(bit); + unsigned long mask = SILC_BIT_MASK(bit); + + if (!bitmap || pos >= bitmap_size) + return FALSE; + + bitmap[pos] |= mask; + return TRUE; +} + +/* Clear bit */ + +SilcBool silc_bit_clear(volatile unsigned long *bitmap, SilcUInt32 bitmap_size, + SilcUInt32 bit) +{ + SilcUInt32 pos = SILC_BIT_POS(bit); + unsigned long mask = SILC_BIT_MASK(bit); + + if (!bitmap || pos >= bitmap_size) + return FALSE; + + bitmap[pos] &= ~mask; + return TRUE; +} + +/* Toggle bit */ + +SilcBool silc_bit_toggle(volatile unsigned long *bitmap, + SilcUInt32 bitmap_size, SilcUInt32 bit) +{ + SilcUInt32 pos = SILC_BIT_POS(bit); + unsigned long mask = SILC_BIT_MASK(bit); + + if (!bitmap || pos >= bitmap_size) + return FALSE; + + bitmap[pos] ^= mask; + return TRUE; +} + +/* Set bit and return old value */ + +int silc_bit_test_and_set(volatile unsigned long *bitmap, + SilcUInt32 bitmap_size, SilcUInt32 bit) +{ + SilcUInt32 pos = SILC_BIT_POS(bit); + unsigned long mask = SILC_BIT_MASK(bit), ret; + + if (!bitmap || pos >= bitmap_size) + return -1; + + ret = bitmap[pos]; + bitmap[pos] ^= mask; + + return (ret & mask) != 0; +} + +/* Clear bit and return old value */ + +int silc_bit_test_and_clear(volatile unsigned long *bitmap, + SilcUInt32 bitmap_size, SilcUInt32 bit) +{ + SilcUInt32 pos = SILC_BIT_POS(bit); + unsigned long mask = SILC_BIT_MASK(bit), ret; + + if (!bitmap || pos >= bitmap_size) + return -1; + + ret = bitmap[pos]; + bitmap[pos] &= ~mask; + + return (ret & mask) != 0; +} + +/* Toggle bit and return old value */ + +int silc_bit_test_and_toggle(volatile unsigned long *bitmap, + SilcUInt32 bitmap_size, SilcUInt32 bit) +{ + SilcUInt32 pos = SILC_BIT_POS(bit); + unsigned long mask = SILC_BIT_MASK(bit), ret; + + if (!bitmap || pos >= bitmap_size) + return -1; + + ret = bitmap[pos]; + bitmap[pos] ^= mask; + + return (ret & mask) != 0; +} + +/* Return bit value */ + +int silc_bit_get(volatile unsigned long *bitmap, SilcUInt32 bitmap_size, + SilcUInt32 bit) +{ + SilcUInt32 pos = SILC_BIT_POS(bit); + unsigned long mask = SILC_BIT_MASK(bit); + + if (!bitmap || pos >= bitmap_size) + return -1; + + return (bitmap[pos] & mask) != 0; +} + +/* Return first set bit number */ + +int silc_bit_ffs(volatile unsigned long *bitmap, SilcUInt32 bitmap_size) +{ + return silc_bit_fns(bitmap, bitmap_size, 0); +} + +/* Return first zero bit number */ + +int silc_bit_ffz(volatile unsigned long *bitmap, SilcUInt32 bitmap_size) +{ + return silc_bit_fnz(bitmap, bitmap_size, 0); +} + +/* Return next set bit number */ + +int silc_bit_fns(volatile unsigned long *bitmap, SilcUInt32 bitmap_size, + SilcUInt32 offset) +{ + register SilcUInt32 i; + + if (!bitmap || offset >= bitmap_size * SILC_BIT_SIZE) + return -1; + + for (i = offset; i < bitmap_size * SILC_BIT_SIZE; i++) + if (bitmap[SILC_BIT_POS(i)] & SILC_BIT_MASK(i)) + return i; + + return -1; +} + +/* Return next zero bit number */ + +int silc_bit_fnz(volatile unsigned long *bitmap, SilcUInt32 bitmap_size, + SilcUInt32 offset) +{ + register SilcUInt32 i; + + if (!bitmap || offset >= bitmap_size * SILC_BIT_SIZE) + return -1; + + for (i = offset; i < bitmap_size * SILC_BIT_SIZE; i++) + if ((bitmap[SILC_BIT_POS(i)] & SILC_BIT_MASK(i)) == 0) + return i; + + return -1; +} + +/* Clear bitmap */ + +void silc_bit_clear_bitmap(volatile unsigned long *bitmap, + SilcUInt32 bitmap_size) +{ + if (!bitmap) + return; + memset((void *)bitmap, 0, bitmap_size * 8); +} diff --git a/lib/silcutil/silcbitops.h b/lib/silcutil/silcbitops.h new file mode 100644 index 00000000..4aa91c2e --- /dev/null +++ b/lib/silcutil/silcbitops.h @@ -0,0 +1,274 @@ +/* + + silcbitops.h + + Author: Pekka Riikonen + + Copyright (C) 2007 Pekka Riikonen + + 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; version 2 of the License. + + 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. + +*/ + +/****h* silcutil/SILC Bit Operations Interface + * + * DESCRIPTION + * + * Bit operations interface. The interface can be used to set, clear and + * find bits in an arbitrarily large bitmap. The interface does not support + * setting the bits atomically. + * + * Example with a pre-allocate bitmap: + * + * // Declare bitmap of size of 500 bits + * SILC_BITMAP_DECLARE(bitmap, 500); + * int bitmap_size = SILC_BITMAP_SIZE(500); + * + * // Set 0 bit + * silc_bit_set(bitmap, bitmap_size, 0); + * + * // Set bit number 100 + * silc_bit_set(bitmap, bitmap_size, 100); + * + * // Find first set bit from the bitmap + * bit = silc_bit_ffs(bitmap, bitmap_size); + * + * // Find next set bit from the bitmap + * bit = silc_bit_fns(bitmap, bitmap_size, bit); + * + * // Clear bit number 100 + * silc_bit_set(bitmap, bitmap_size, 100); + * + ***/ + +#ifndef SILCBITOPS_H +#define SILCBITOPS_H + +#define SILC_BIT_SIZE (SILC_SIZEOF_LONG * 8) + +/****d* silcutil/SilcBitOpAPI/SILC_BITMAP_DECLARE + * + * NAME + * + * #define SILC_BITMAP_DECLARE(name, bits) + * + * DESCRIPTION + * + * Macro that can be used to declare a pre-allocated bitmap named `name' of + * size of `bits' many bits. + * + ***/ +#define SILC_BITMAP_DECLARE(name, bits) \ + unsigned long name[SILC_BITMAP_SIZE(bits)] + +/****d* silcutil/SilcBitOpAPI/SILC_BITMAP_SIZE + * + * NAME + * + * #define SILC_BITMAP_SIZE(bits) + * + * DESCRIPTION + * + * Macro that returns the size of a bitmap array of size of `bits' many + * bits. The returned size can be given as argument to the SILC Bit + * Operations API functions. + * + ***/ +#define SILC_BITMAP_SIZE(bits) (((bits) + SILC_BIT_SIZE) / SILC_BIT_SIZE) + +/****f* silcutil/SilcBitOpAPI/silc_bit_set + * + * SYNOPSIS + * + * SilcBool silc_bit_set(volatile unsigned long *bitmap, + * SilcUInt32 bitmap_size, SilcUInt32 bit); + * + * DESCRIPTION + * + * Set bit number `bit' in the `bitmap' of size of `bitmap_size'. Returns + * FALSE on error. + * + ***/ +SilcBool silc_bit_set(volatile unsigned long *bitmap, SilcUInt32 bitmap_size, + SilcUInt32 bit); + +/****f* silcutil/SilcBitOpAPI/silc_bit_clear + * + * SYNOPSIS + * + * SilcBool silc_bit_clear(volatile unsigned long *bitmap, + * SilcUInt32 bitmap_size, SilcUInt32 bit); + * + * DESCRIPTION + * + * Clear bit number `bit' in the `bitmap' of size of `bitmap_size'. + * Returns FALSE on error. + * + ***/ +SilcBool silc_bit_clear(volatile unsigned long *bitmap, SilcUInt32 bitmap_size, + SilcUInt32 bit); + +/****f* silcutil/SilcBitOpAPI/silc_bit_toggle + * + * SYNOPSIS + * + * SilcBool silc_bit_toggle(volatile unsigned long *bitmap, + * SilcUInt32 bitmap_size, SilcUInt32 bit); + * + * DESCRIPTION + * + * Toggle bit number `bit' in the `bitmap' of size of `bitmap_size'. + * Returns FALSE on error. + * + ***/ +SilcBool silc_bit_toggle(volatile unsigned long *bitmap, + SilcUInt32 bitmap_size, SilcUInt32 bit); + +/****f* silcutil/SilcBitOpAPI/silc_bit_test_and_set + * + * SYNOPSIS + * + * int silc_bit_test_and_set(volatile unsigned long *bitmap, + * SilcUInt32 bitmap_size, SilcUInt32 bit); + * + * DESCRIPTION + * + * Set bit number `bit' in the `bitmap' of size of `bitmap_size' and + * return the value before setting. Returns -1 on error. + * + ***/ +int silc_bit_test_and_set(volatile unsigned long *bitmap, + SilcUInt32 bitmap_size, SilcUInt32 bit); + +/****f* silcutil/SilcBitOpAPI/silc_bit_test_and_clear + * + * SYNOPSIS + * + * int silc_bit_test_and_clear(volatile unsigned long *bitmap, + * SilcUInt32 bitmap_size, SilcUInt32 bit); + * + * DESCRIPTION + * + * Clear bit number `bit' in the `bitmap' of size of `bitmap_size' and + * return the value before setting. Returns -1 on error. + * + ***/ +int silc_bit_test_and_clear(volatile unsigned long *bitmap, + SilcUInt32 bitmap_size, SilcUInt32 bit); + +/****f* silcutil/SilcBitOpAPI/silc_bit_test_and_toggle + * + * SYNOPSIS + * + * int silc_bit_test_and_toggle(volatile unsigned long *bitmap, + * SilcUInt32 bitmap_size, SilcUInt32 bit); + * + * DESCRIPTION + * + * Toggle bit number `bit' in the `bitmap' of size of `bitmap_size' and + * return the value before setting. Returns -1 on error. + * + ***/ +int silc_bit_test_and_toggle(volatile unsigned long *bitmap, + SilcUInt32 bitmap_size, SilcUInt32 bit); + +/****f* silcutil/SilcBitOpAPI/silc_bit_get + * + * SYNOPSIS + * + * int silc_bit_get(volatile unsigned long *bitmap, SilcUInt32 bitmap_size, + * ,SilcUInt32 bit); + * + * DESCRIPTION + * + * Returns the value of the bit number `bit' or -1 on error. + * + ***/ +int silc_bit_get(volatile unsigned long *bitmap, SilcUInt32 bitmap_size, + SilcUInt32 bit); + +/****f* silcutil/SilcBitOpAPI/silc_bit_ffs + * + * SYNOPSIS + * + * int silc_bit_ffs(volatile unsigned long *bitmap, SilcUInt32 bitmap_size); + * + * DESCRIPTION + * + * Returns the bit number of the first set bit in the `bitmap' of size + * of `bitmap_size'. Returns -1 on error or there were no set bits. + * + ***/ +int silc_bit_ffs(volatile unsigned long *bitmap, SilcUInt32 bitmap_size); + +/****f* silcutil/SilcBitOpAPI/silc_bit_ffz + * + * SYNOPSIS + * + * int silc_bit_ffz(volatile unsigned long *bitmap, SilcUInt32 bitmap_size); + * + * DESCRIPTION + * + * Returns the bit number of the first zero bit in the `bitmap' of size + * of `bitmap_size'. Returns -1 on error or there were no zero bits. + * + ***/ +int silc_bit_ffz(volatile unsigned long *bitmap, SilcUInt32 bitmap_size); + +/****f* silcutil/SilcBitOpAPI/silc_bit_fns + * + * SYNOPSIS + * + * int silc_bit_fns(volatile unsigned long *bitmap, SilcUInt32 bitmap_size, + * SilcUInt32 offset); + * + * DESCRIPTION + * + * Returns the bit number of the next set bit in the `bitmap' of size + * of `bitmap_size' starting at bit `offset'. Returns -1 on error or + * there were no more set bits. + * + ***/ +int silc_bit_fns(volatile unsigned long *bitmap, SilcUInt32 bitmap_size, + SilcUInt32 offset); + +/****f* silcutil/SilcBitOpAPI/silc_bit_fnz + * + * SYNOPSIS + * + * int silc_bit_fnz(volatile unsigned long *bitmap, SilcUInt32 bitmap_size, + * SilcUInt32 offset); + * + * DESCRIPTION + * + * Returns the bit number of the next zero bit in the `bitmap' of size + * of `bitmap_size' starting at bit `offset'. Returns -1 on error or + * there were no more zero bits. + * + ***/ +int silc_bit_fnz(volatile unsigned long *bitmap, SilcUInt32 bitmap_size, + SilcUInt32 offset); + +/****f* silcutil/SilcBitOpAPI/silc_bit_clear_bitmap + * + * SYNOPSIS + * + * void silc_bit_clear_bitmap(volatile unsigned long *bitmap, + * SilcUInt32 bitmap_size); + * + * DESCRIPTION + * + * Clears the whole bitmap. + * + ***/ +void silc_bit_clear_bitmap(volatile unsigned long *bitmap, + SilcUInt32 bitmap_size); + +#endif /* SILCBITOPS_H */ diff --git a/lib/silcutil/tests/Makefile.am b/lib/silcutil/tests/Makefile.am index f6654a19..21511a01 100644 --- a/lib/silcutil/tests/Makefile.am +++ b/lib/silcutil/tests/Makefile.am @@ -21,7 +21,7 @@ bin_PROGRAMS = test_silcstrutil test_silcstringprep test_silchashtable \ test_silclist test_silcfsm test_silcasync test_silcschedule \ test_silcnet test_silcstack test_silcmime test_silcfdstream \ test_silcatomic test_silcmutex test_silctime test_silcthread \ - test_silcdll test_silcenv test_silctimer + test_silcdll test_silcenv test_silctimer test_silcbitops test_silcstrutil_SOURCES = test_silcstrutil.c test_silcstringprep_SOURCES = test_silcstringprep.c @@ -41,6 +41,7 @@ test_silcthread_SOURCES = test_silcthread.c test_silcdll_SOURCES = test_silcdll.c test_silcenv_SOURCES = test_silcenv.c test_silctimer_SOURCES = test_silctimer.c +test_silcbitops_SOURCES = test_silcbitops.c LIBS = $(SILC_COMMON_LIBS) LDADD = -L.. -L../.. -lsilc diff --git a/lib/silcutil/tests/test_silcbitops.c b/lib/silcutil/tests/test_silcbitops.c new file mode 100644 index 00000000..adbd8d08 --- /dev/null +++ b/lib/silcutil/tests/test_silcbitops.c @@ -0,0 +1,137 @@ +/* Bit operation tests */ + +#include "silc.h" + +int main(int argc, char **argv) +{ + SilcBool success = FALSE; + SILC_BITMAP_DECLARE(bitmap, 500); + int size = SILC_BITMAP_SIZE(500), bit; + + if (argc > 1 && !strcmp(argv[1], "-d")) { + silc_log_debug(TRUE); + silc_log_quick(TRUE); + silc_log_debug_hexdump(TRUE); + silc_log_set_debug_string("*bit*"); + } + + silc_bit_clear_bitmap(bitmap, size); + + SILC_LOG_DEBUG(("Setting bit 0")); + if (!silc_bit_set(bitmap, size, 0)) + goto err; + bit = silc_bit_get(bitmap, size, 0); + SILC_LOG_DEBUG(("Get bit 0: %d", bit)); + if (bit < 0) + goto err; + if (bit != 1) + goto err; + + SILC_LOG_DEBUG(("Setting bit 100")); + if (!silc_bit_set(bitmap, size, 100)) + goto err; + bit = silc_bit_get(bitmap, size, 100); + SILC_LOG_DEBUG(("Get bit 100: %d", bit)); + if (bit < 0) + goto err; + if (bit != 1) + goto err; + + SILC_LOG_DEBUG(("Clear bit 100")); + if (!silc_bit_clear(bitmap, size, 100)) + goto err; + bit = silc_bit_get(bitmap, size, 100); + SILC_LOG_DEBUG(("Get bit 100: %d", bit)); + if (bit < 0) + goto err; + if (bit != 0) + goto err; + + SILC_LOG_DEBUG(("Toggle bit 99")); + if (!silc_bit_toggle(bitmap, size, 99)) + goto err; + bit = silc_bit_get(bitmap, size, 99); + SILC_LOG_DEBUG(("Get bit 99: %d", bit)); + if (bit < 0) + goto err; + if (bit != 1) + goto err; + + SILC_LOG_DEBUG(("Test and toggle bit 499")); + bit = silc_bit_test_and_toggle(bitmap, size, 499); + if (bit != 0) + goto err; + bit = silc_bit_get(bitmap, size, 499); + SILC_LOG_DEBUG(("Get bit 499: %d", bit)); + if (bit < 0) + goto err; + if (bit != 1) + goto err; + + SILC_LOG_DEBUG(("Test and set bit 10")); + bit = silc_bit_test_and_set(bitmap, size, 10); + if (bit != 0) + goto err; + bit = silc_bit_get(bitmap, size, 10); + SILC_LOG_DEBUG(("Get bit 10: %d", bit)); + if (bit < 0) + goto err; + if (bit != 1) + goto err; + + SILC_LOG_DEBUG(("Test overflow")); + if (silc_bit_set(bitmap, size, 1500)) + goto err; + SILC_LOG_DEBUG(("Overflow detected")); + + SILC_LOG_DEBUG(("Find first set bit")); + bit = silc_bit_ffs(bitmap, size); + SILC_LOG_DEBUG(("First set bit: %d", bit)); + if (bit != 0) + goto err; + + SILC_LOG_DEBUG(("Find next set bit")); + bit = silc_bit_fns(bitmap, size, bit + 1); + SILC_LOG_DEBUG(("Next set bit: %d", bit)); + if (bit != 10) + goto err; + + SILC_LOG_DEBUG(("Find all set bits")); + bit = 0; + do { + bit = silc_bit_fns(bitmap, size, bit); + if (bit != -1) { + SILC_LOG_DEBUG(("Set bit: %d", bit)); + bit++; + } + } while (bit != -1); + + SILC_LOG_DEBUG(("Find first zero bit")); + bit = silc_bit_ffz(bitmap, size); + SILC_LOG_DEBUG(("First zero bit: %d", bit)); + if (bit != 1) + goto err; + + SILC_LOG_DEBUG(("Find next zero bit")); + bit = silc_bit_fnz(bitmap, size, bit + 1); + SILC_LOG_DEBUG(("Next zero bit: %d", bit)); + if (bit != 2) + goto err; + + SILC_LOG_DEBUG(("Clear bitmap")); + silc_bit_clear_bitmap(bitmap, size); + + SILC_LOG_DEBUG(("Check for set bits")); + bit = silc_bit_ffs(bitmap, size); + if (bit > 0) + goto err; + SILC_LOG_DEBUG(("No set bits")); + + success = TRUE; + + err: + SILC_LOG_DEBUG(("Testing was %s", success ? "SUCCESS" : "FAILURE")); + fprintf(stderr, "Testing was %s\n", success ? "SUCCESS" : "FAILURE"); + + return success; +} -- 2.24.0