123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552 |
- /*
- bit_array.h
- project: bit array C library
- url: https://github.com/noporpoise/BitArray/
- maintainer: Isaac Turner <turner.isaac@gmail.com>
- license: Public Domain, no warranty
- date: Sep 2014
- */
- #ifndef BIT_ARRAY_HEADER_SEEN
- #define BIT_ARRAY_HEADER_SEEN
- #include <stdio.h>
- #include <inttypes.h>
- #include "bit_macros.h"
- typedef struct BIT_ARRAY BIT_ARRAY;
- // 64 bit words
- typedef uint64_t word_t, word_addr_t, bit_index_t;
- typedef uint8_t word_offset_t; // Offset within a 64 bit word
- #define BIT_INDEX_MIN 0
- #define BIT_INDEX_MAX (~(bit_index_t)0)
- #ifdef __cplusplus
- extern "C" {
- #endif
- //
- // Structs
- //
- struct BIT_ARRAY
- {
- word_t* words;
- bit_index_t num_of_bits;
- // Number of words used -- this is just round_up(num_of_bits / 64)
- // if num_of_bits == 0, this is 0
- word_addr_t num_of_words;
- // For more efficient allocation we use realloc only to double size --
- // not for adding every word. Initial size is INIT_CAPACITY_WORDS.
- word_addr_t capacity_in_words;
- };
- //
- // Basics: Constructor, destructor, get length, resize
- //
- // Constructor - create a new bit array of length nbits
- BIT_ARRAY* bit_array_create(bit_index_t nbits);
- // Destructor - free the memory used for a bit array
- void bit_array_free(BIT_ARRAY* bitarray);
- // Allocate using existing struct
- BIT_ARRAY* bit_array_alloc(BIT_ARRAY* bitarr, bit_index_t nbits);
- void bit_array_dealloc(BIT_ARRAY* bitarr);
- // Get length of bit array
- bit_index_t bit_array_length(const BIT_ARRAY* bit_arr);
- // Change the size of a bit array. Enlarging an array will add zeros
- // to the end of it. Returns 1 on success, 0 on failure (e.g. not enough memory)
- char bit_array_resize(BIT_ARRAY* bitarr, bit_index_t new_num_of_bits);
- // If bitarr length < num_bits, resizes to num_bits
- char bit_array_ensure_size(BIT_ARRAY* bitarr, bit_index_t ensure_num_of_bits);
- // Same as above but exit with an error message if out of memory
- void bit_array_resize_critical(BIT_ARRAY* bitarr, bit_index_t num_of_bits);
- void bit_array_ensure_size_critical(BIT_ARRAY* bitarr, bit_index_t num_of_bits);
- //
- // Macros
- //
- //
- // Get, set, clear, assign and toggle individual bits
- // Macros for fast access -- beware: no bounds checking
- //
- #define bit_array_get(arr,i) bitset_get((arr)->words, i)
- #define bit_array_set(arr,i) bitset_set((arr)->words, i)
- #define bit_array_clear(arr,i) bitset_del((arr)->words, i)
- #define bit_array_toggle(arr,i) bitset_tgl((arr)->words, i)
- // c must be 0 or 1
- #define bit_array_assign(arr,i,c) bitset_cpy((arr)->words,i,c)
- //
- // Get, set, clear, assign and toggle individual bits
- // "Safe": use assert() to check bounds
- //
- // Get the value of a bit (returns 0 or 1)
- char bit_array_get_bit(const BIT_ARRAY* bitarr, bit_index_t b);
- void bit_array_set_bit(BIT_ARRAY* bitarr, bit_index_t b);
- void bit_array_clear_bit(BIT_ARRAY* bitarr, bit_index_t b);
- void bit_array_toggle_bit(BIT_ARRAY* bitarr, bit_index_t b);
- // If char c != 0, set bit; otherwise clear bit
- void bit_array_assign_bit(BIT_ARRAY* bitarr, bit_index_t b, char c);
- //
- // "Resizing": enlarge array if needed
- //
- char bit_array_rget(BIT_ARRAY* bitarr, bit_index_t b);
- void bit_array_rset(BIT_ARRAY* bitarr, bit_index_t b);
- void bit_array_rclear(BIT_ARRAY* bitarr, bit_index_t b);
- void bit_array_rtoggle(BIT_ARRAY* bitarr, bit_index_t b);
- void bit_array_rassign(BIT_ARRAY* bitarr, bit_index_t b, char c);
- //
- // Set, clear and toggle several bits at once
- //
- // Set multiple bits at once.
- // e.g. set bits 1, 20 & 31: bit_array_set_bits(bitarr, 3, 1,20,31);
- // Note: variable args are of type unsigned int
- void bit_array_set_bits(BIT_ARRAY* bitarr, size_t n, ...);
- // Clear multiple bits at once.
- // e.g. clear bits 1, 20 & 31: bit_array_clear_bits(bitarr, 3, 1,20,31);
- // Note: variable args are of type unsigned int
- void bit_array_clear_bits(BIT_ARRAY* bitarr, size_t n, ...);
- // Toggle multiple bits at once
- // e.g. toggle bits 1, 20 & 31: bit_array_toggle_bits(bitarr, 3, 1,20,31);
- // Note: variable args are of type unsigned int
- void bit_array_toggle_bits(BIT_ARRAY* bitarr, size_t n, ...);
- //
- // Set, clear and toggle all bits in a region
- //
- // Set all the bits in a region
- void bit_array_set_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len);
- // Clear all the bits in a region
- void bit_array_clear_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len);
- // Toggle all the bits in a region
- void bit_array_toggle_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len);
- //
- // Set, clear and toggle all bits at once
- //
- // Set all bits in this array to 1
- void bit_array_set_all(BIT_ARRAY* bitarr);
- // Set all bits in this array to 0
- void bit_array_clear_all(BIT_ARRAY* bitarr);
- // Set all 1 bits to 0, and all 0 bits to 1
- void bit_array_toggle_all(BIT_ARRAY* bitarr);
- //
- // Get / set a word of a given size
- //
- // First bit is in the least significant bit position
- // start index must be within the range of the bit array (0 <= x < length)
- uint64_t bit_array_get_word64(const BIT_ARRAY* bitarr, bit_index_t start);
- uint32_t bit_array_get_word32(const BIT_ARRAY* bitarr, bit_index_t start);
- uint16_t bit_array_get_word16(const BIT_ARRAY* bitarr, bit_index_t start);
- uint8_t bit_array_get_word8(const BIT_ARRAY* bitarr, bit_index_t start);
- uint64_t bit_array_get_wordn(const BIT_ARRAY* bitarr, bit_index_t start, int n);
- // Set 64 bits at once from a particular start position
- void bit_array_set_word64(BIT_ARRAY* bitarr, bit_index_t start, uint64_t word);
- void bit_array_set_word32(BIT_ARRAY* bitarr, bit_index_t start, uint32_t word);
- void bit_array_set_word16(BIT_ARRAY* bitarr, bit_index_t start, uint16_t word);
- void bit_array_set_word8(BIT_ARRAY* bitarr, bit_index_t start, uint8_t byte);
- void bit_array_set_wordn(BIT_ARRAY* bitarr, bit_index_t start, uint64_t word, int n);
- //
- // Number of bits set
- //
- // Get the number of bits set (hamming weight)
- bit_index_t bit_array_num_bits_set(const BIT_ARRAY* bitarr);
- // Get the number of bits not set (length - hamming weight)
- bit_index_t bit_array_num_bits_cleared(const BIT_ARRAY* bitarr);
- // Get the number of bits set in on array and not the other. This is equivalent
- // to hamming weight of the XOR when the two arrays are the same length.
- // e.g. 10101 vs 00111 => hamming distance 2 (XOR is 10010)
- bit_index_t bit_array_hamming_distance(const BIT_ARRAY* arr1,
- const BIT_ARRAY* arr2);
- // Parity - returns 1 if odd number of bits set, 0 if even
- char bit_array_parity(const BIT_ARRAY* bitarr);
- //
- // Find indices of set/clear bits
- //
- // Find the index of the next bit that is set, at or after `offset`
- // Returns 1 if a bit is set, otherwise 0
- // Index of next set bit is stored in the integer pointed to by result
- // If no next bit is set result is not changed
- char bit_array_find_next_set_bit(const BIT_ARRAY* bitarr, bit_index_t offset,
- bit_index_t* result);
- // Find the index of the next bit that is NOT set, at or after `offset`
- // Returns 1 if a bit is NOT set, otherwise 0
- // Index of next zero bit is stored in the integer pointed to by `result`
- // If no next bit is zero, value at `result` is not changed
- char bit_array_find_next_clear_bit(const BIT_ARRAY* bitarr, bit_index_t offset,
- bit_index_t* result);
- // Find the index of the previous bit that is set, before offset.
- // Returns 1 if a bit is set, otherwise 0
- // Index of previous set bit is stored in the integer pointed to by `result`
- // If no previous bit is set result is not changed
- char bit_array_find_prev_set_bit(const BIT_ARRAY* bitarr, bit_index_t offset,
- bit_index_t* result);
- // Find the index of the previous bit that is NOT set, before offset.
- // Returns 1 if a bit is clear, otherwise 0
- // Index of previous zero bit is stored in the integer pointed to by `result`
- // If no previous bit is zero result is not changed
- char bit_array_find_prev_clear_bit(const BIT_ARRAY* bitarr, bit_index_t offset,
- bit_index_t* result);
- // Find the index of the first bit that is set.
- // Returns 1 if a bit is set, otherwise 0
- // Index of first set bit is stored in the integer pointed to by `result`
- // If no bit is set result is not changed
- char bit_array_find_first_set_bit(const BIT_ARRAY* bitarr, bit_index_t* result);
- // Find the index of the first bit that is NOT set.
- // Returns 1 if a bit is clear, otherwise 0
- // Index of first zero bit is stored in the integer pointed to by `result`
- // If no bit is zero result is not changed
- char bit_array_find_first_clear_bit(const BIT_ARRAY* bitarr, bit_index_t* result);
- // Find the index of the last bit that is set.
- // Returns 1 if a bit is set, otherwise 0
- // Index of last set bit is stored in the integer pointed to by `result`
- // If no bit is set result is not changed
- char bit_array_find_last_set_bit(const BIT_ARRAY* bitarr, bit_index_t* result);
- // Find the index of the last bit that is NOT set.
- // Returns 1 if a bit is clear, otherwise 0
- // Index of last zero bit is stored in the integer pointed to by `result`
- // If no bit is zero result is not changed
- char bit_array_find_last_clear_bit(const BIT_ARRAY* bitarr, bit_index_t* result);
- //
- // Sorting
- //
- // Put all the 0s before all the 1s
- void bit_array_sort_bits(BIT_ARRAY* bitarr);
- // Put all the 1s before all the 0s
- void bit_array_sort_bits_rev(BIT_ARRAY* bitarr);
- //
- // String and printing methods
- //
- // Construct a BIT_ARRAY from a string.
- void bit_array_from_str(BIT_ARRAY* bitarr, const char* bitstr);
- // Construct a BIT_ARRAY from a substring with given on and off characters.
- void bit_array_from_substr(BIT_ARRAY* bitarr, bit_index_t offset,
- const char* str, size_t len,
- const char *on, const char *off, char left_to_right);
- // Takes a char array to write to. `str` must be bitarr->num_of_bits+1 in
- // length. Terminates string with '\0'
- char* bit_array_to_str(const BIT_ARRAY* bitarr, char* str);
- char* bit_array_to_str_rev(const BIT_ARRAY* bitarr, char* str);
- // Get a string representations for a given region, using given on/off
- // characters.
- // Note: does not null-terminate
- void bit_array_to_substr(const BIT_ARRAY* bitarr,
- bit_index_t start, bit_index_t length,
- char* str, char on, char off, char left_to_right);
- // Print this array to a file stream. Prints '0's and '1'. Doesn't print
- // newline.
- void bit_array_print(const BIT_ARRAY* bitarr, FILE* fout);
- // Print a string representations for a given region, using given on/off
- // characters. Reverse prints from highest to lowest -- this is useful for
- // printing binary numbers
- void bit_array_print_substr(const BIT_ARRAY* bitarr,
- bit_index_t start, bit_index_t length,
- FILE* fout, char on, char off, char left_to_right);
- //
- // Decimal
- //
- // Get bit array as decimal str (e.g. 0b1101 -> "13")
- size_t bit_array_to_decimal(const BIT_ARRAY *bitarr, char *str, size_t len);
- // Return number of characters used
- size_t bit_array_from_decimal(BIT_ARRAY *bitarr, const char* decimal);
- //
- // Hexidecimal
- //
- // Loads array from hex string
- // Returns the number of bits loaded (will be chars rounded up to multiple of 8)
- // (0 on failure)
- bit_index_t bit_array_from_hex(BIT_ARRAY* bitarr, bit_index_t offset,
- const char* str, size_t len);
- // Returns number of characters written
- size_t bit_array_to_hex(const BIT_ARRAY* bitarr,
- bit_index_t start, bit_index_t length,
- char* str, char uppercase);
- // Print bit array as hex
- size_t bit_array_print_hex(const BIT_ARRAY* bitarr,
- bit_index_t start, bit_index_t length,
- FILE* fout, char uppercase);
- //
- // Clone and copy
- //
- // Copy a BIT_ARRAY struct and the data it holds - returns pointer to new object
- #define bit_array_dup bit_array_clone
- BIT_ARRAY* bit_array_clone(const BIT_ARRAY* bitarr);
- // Copy bits from one array to another
- // Note: use MACRO bit_array_copy
- // Destination and source can be the same bit_array and
- // src/dst regions can overlap
- void bit_array_copy(BIT_ARRAY* dst, bit_index_t dstindx,
- const BIT_ARRAY* src, bit_index_t srcindx,
- bit_index_t length);
- // copy all of src to dst. dst is resized to match src.
- void bit_array_copy_all(BIT_ARRAY* dst, const BIT_ARRAY* src);
- //
- // Logic operators
- //
- // BIT_ARRAYs can all be different or the same object
- // dest array will be resized if it is too short
- //
- void bit_array_and(BIT_ARRAY* dest, const BIT_ARRAY* src1, const BIT_ARRAY* src2);
- void bit_array_or (BIT_ARRAY* dest, const BIT_ARRAY* src1, const BIT_ARRAY* src2);
- void bit_array_xor(BIT_ARRAY* dest, const BIT_ARRAY* src1, const BIT_ARRAY* src2);
- void bit_array_not(BIT_ARRAY* dest, const BIT_ARRAY* src);
- //
- // Comparisons
- //
- // Note: (bit_array_cmp(a,b) == 0) <=> (bit_array_cmp_big_endian(a,b) == 0)
- // comparison functions return:
- // 1 iff bitarr1 > bitarr2
- // 0 iff bitarr1 == bitarr2
- // -1 iff bitarr1 < bitarr2
- // Compare two bit arrays by value stored, with index 0 being the Least
- // Significant Bit (LSB). Arrays do not have to be the same length.
- // Example: ..0101 (5) > ...0011 (3) [index 0 is LSB at right hand side]
- int bit_array_cmp(const BIT_ARRAY* bitarr1, const BIT_ARRAY* bitarr2);
- // Compare two bit arrays by value stored, with index 0 being the Most
- // Significant Bit (MSB). Arrays do not have to be the same length.
- // Example: 10.. > 01.. [index 0 is MSB at left hand side]
- int bit_array_cmp_big_endian(const BIT_ARRAY* bitarr1, const BIT_ARRAY* bitarr2);
- // compare bitarr with (bitarr2 << pos)
- int bit_array_cmp_words(const BIT_ARRAY *bitarr,
- bit_index_t pos, const BIT_ARRAY *bitarr2);
- //
- // Shift, interleave, reverse
- //
- // Shift array left/right. If fill is zero, filled with 0, otherwise 1
- void bit_array_shift_right(BIT_ARRAY* bitarr, bit_index_t shift_dist, char fill);
- void bit_array_shift_left (BIT_ARRAY* bitarr, bit_index_t shift_dist, char fill);
- // shift left without losing any bits. Resizes bitarr.
- void bit_array_shift_left_extend(BIT_ARRAY* bitarr, bit_index_t shift_dist,
- char fill);
- // Cyclic shift
- void bit_array_cycle_right(BIT_ARRAY* bitarr, bit_index_t dist);
- void bit_array_cycle_left (BIT_ARRAY* bitarr, bit_index_t dist);
- // Interleave
- // dst cannot point to the same bit array as src1 or src2
- // src1, src2 may point to the same bit array
- // abcd 1234 -> a1b2c3d4
- // 0011 0000 -> 00001010
- // 1111 0000 -> 10101010
- // 0101 1010 -> 01100110
- // Extends dst if it is too short, but does not shrink it if it is too long
- // if dst is longer than length(src1)+length(src2), the end bits are not altered
- void bit_array_interleave(BIT_ARRAY* dst,
- const BIT_ARRAY* src1,
- const BIT_ARRAY* src2);
- // Reverse the whole array or part of it
- void bit_array_reverse(BIT_ARRAY* bitarr);
- void bit_array_reverse_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len);
- //
- // Numeric
- //
- // Returns 1 on sucess, 0 if value in array is too big
- char bit_array_as_num(const BIT_ARRAY* bitarr, uint64_t* result);
- // 1 iff bitarr > value
- // 0 iff bitarr == value
- // -1 iff bitarr < value
- int bit_array_cmp_uint64(const BIT_ARRAY* bitarr, uint64_t value);
- //
- // Arithmetic
- //
- // bitarr will be extended if needed
- void bit_array_add_uint64(BIT_ARRAY* bitarr, uint64_t value);
- // Add `add` to `bitarr` at `pos` -- same as:
- // bitarr + (add << pos)
- // where pos can be bigger than the length of the array (bitarr will be resized)
- void bit_array_add_word(BIT_ARRAY *bitarr, bit_index_t pos, uint64_t add);
- // Add `add` to `bitarr` at `pos`
- void bit_array_add_words(BIT_ARRAY *bitarr, bit_index_t pos, const BIT_ARRAY *add);
- // If value is greater than bitarr, bitarr is not changed and 0 is returned
- // Returns 1 on success, 0 if value > bitarr
- char bit_array_sub_uint64(BIT_ARRAY* bitarr, uint64_t value);
- // minus `minus` from `bitarr` at `pos` -- same as:
- // bitarr + (minus << pos)
- // Returns 1 on success, 0 if value > bitarr
- char bit_array_sub_word(BIT_ARRAY *bitarr, bit_index_t pos, word_t minus);
- // minus `minus` from `bitarr` at `pos`
- // Returns 1 on success, 0 if value > bitarr
- char bit_array_sub_words(BIT_ARRAY* bitarr, bit_index_t pos, BIT_ARRAY* minus);
- // Multiply by some value
- void bit_array_mul_uint64(BIT_ARRAY *bitarr, uint64_t multiplier);
- // bitarr = round_down(bitarr / divisor)
- // rem = bitarr % divisor
- void bit_array_div_uint64(BIT_ARRAY *bitarr, uint64_t divisor, uint64_t *rem);
- //
- // Arithmetic between arrays
- //
- // dst = src1 + src2
- // src1, src2 and dst can all be the same BIT_ARRAY
- // If dst is shorter than either of src1, src2, it is enlarged
- void bit_array_add(BIT_ARRAY* dst, const BIT_ARRAY* src1, const BIT_ARRAY* src2);
- // dst = src1 - src2
- // src1, src2 and dst can all be the same BIT_ARRAY
- // If dst is shorter than src1, it will be extended to be as long as src1
- // src1 must be greater than or equal to src2 (src1 >= src2)
- void bit_array_subtract(BIT_ARRAY* dst,
- const BIT_ARRAY* src1, const BIT_ARRAY* src2);
- // dst = src1 * src2
- // Pointers cannot all point to the same BIT_ARRAY
- void bit_array_multiply(BIT_ARRAY *dst, BIT_ARRAY *src1, BIT_ARRAY *src2);
- // Results in:
- // quotient = dividend / divisor
- // dividend = dividend % divisor
- // (dividend is used to return the remainder)
- void bit_array_divide(BIT_ARRAY *dividend, BIT_ARRAY *quotient, BIT_ARRAY *divisor);
- //
- // Read/Write bit_array to a file
- //
- // File format is [8 bytes: for number of elements in array][data]
- // Number of bytes of data is: (int)((num_of_bits + 7) / 8)
- //
- // Saves bit array to a file
- // returns the number of bytes written
- bit_index_t bit_array_save(const BIT_ARRAY* bitarr, FILE* f);
- // Reads bit array from a file. bitarr is resized and filled.
- // Returns 1 on success, 0 on failure
- char bit_array_load(BIT_ARRAY* bitarr, FILE* f);
- //
- // Hash function
- //
- // Pass seed as 0 on first call, pass previous hash value if rehashing due
- // to a collision
- // Using bob jenkins hash lookup3
- uint64_t bit_array_hash(const BIT_ARRAY* bitarr, uint64_t seed);
- //
- // Randomness
- //
- // Set bits randomly with probability prob : 0 <= prob <= 1
- void bit_array_random(BIT_ARRAY* bitarr, float prob);
- // Shuffle the bits in an array randomly
- void bit_array_shuffle(BIT_ARRAY* bitarr);
- // Get the next permutation of an array with a fixed size and given number of
- // bits set. Also known as next lexicographic permutation.
- // Given a bit array find the next lexicographic orginisation of the bits
- // Number of possible combinations given by (size choose bits_set) i.e. nCk
- // 00011 -> 00101 -> 00110 -> 01001 -> 01010 ->
- // 01100 -> 10001 -> 10010 -> 10100 -> 11000 -> 00011 (back to start)
- void bit_array_next_permutation(BIT_ARRAY* bitarr);
- //
- // Generally useful functions
- //
- // Generalised 'binary to string' function
- // Adds bits to the string in order of lsb to msb
- // e.g. 0b11010 (26 in decimal) would come out as "01011"
- char* bit_array_word2str(const void *ptr, size_t num_of_bits, char *str);
- // Same as above but in reverse
- char* bit_array_word2str_rev(const void *ptr, size_t num_of_bits, char *str);
- #ifdef __cplusplus
- }
- #endif
- #endif
|