From f5c4671bfbad96bf346bd7e9a21fc4317b4959df Mon Sep 17 00:00:00 2001 From: Indrajith K L Date: Sat, 3 Dec 2022 17:00:20 +0530 Subject: Adds most of the tools --- v_windows/v/old/vlib/bitfield/README.md | 11 + v_windows/v/old/vlib/bitfield/bitfield.v | 569 ++++++++++++++++++++++++++ v_windows/v/old/vlib/bitfield/bitfield_test.v | 333 +++++++++++++++ 3 files changed, 913 insertions(+) create mode 100644 v_windows/v/old/vlib/bitfield/README.md create mode 100644 v_windows/v/old/vlib/bitfield/bitfield.v create mode 100644 v_windows/v/old/vlib/bitfield/bitfield_test.v (limited to 'v_windows/v/old/vlib/bitfield') diff --git a/v_windows/v/old/vlib/bitfield/README.md b/v_windows/v/old/vlib/bitfield/README.md new file mode 100644 index 0000000..8b82c4c --- /dev/null +++ b/v_windows/v/old/vlib/bitfield/README.md @@ -0,0 +1,11 @@ +# Quickstart + +`bitfield` is a module for +manipulating arrays of bits, i.e. series of zeroes and ones spread across an +array of storage units (unsigned 32-bit integers). + +## BitField structure + +Bit arrays are stored in data structures called 'BitField'. The structure is +'opaque', i.e. its internals are not available to the end user. This module +provides API (functions and methods) for accessing and modifying bit arrays. diff --git a/v_windows/v/old/vlib/bitfield/bitfield.v b/v_windows/v/old/vlib/bitfield/bitfield.v new file mode 100644 index 0000000..9ed4e2b --- /dev/null +++ b/v_windows/v/old/vlib/bitfield/bitfield.v @@ -0,0 +1,569 @@ +module bitfield + +/* +bitfield is a module for +manipulating arrays of bits, i.e. series of zeroes and ones spread across an +array of storage units (unsigned 32-bit integers). + +BitField structure +------------------ + +Bit arrays are stored in data structures called 'BitField'. The structure is +'opaque', i.e. its internals are not available to the end user. This module +provides API (functions and methods) for accessing and modifying bit arrays. +*/ +pub struct BitField { +mut: + size int + // field *u32 + field []u32 +} + +// helper functions +const ( + slot_size = 32 +) + +// from_bytes converts a byte array into a bitfield. +// [0x0F, 0x01] => 0000 1111 0000 0001 +pub fn from_bytes(input []byte) BitField { + mut output := new(input.len * 8) + for i, b in input { + mut ob := byte(0) + if b & 0b10000000 > 0 { + ob |= 0b00000001 + } + if b & 0b01000000 > 0 { + ob |= 0b00000010 + } + if b & 0b00100000 > 0 { + ob |= 0b00000100 + } + if b & 0b00010000 > 0 { + ob |= 0b00001000 + } + if b & 0b00001000 > 0 { + ob |= 0b00010000 + } + if b & 0b00000100 > 0 { + ob |= 0b00100000 + } + if b & 0b00000010 > 0 { + ob |= 0b01000000 + } + if b & 0b00000001 > 0 { + ob |= 0b10000000 + } + output.field[i / 4] |= u32(ob) << ((i % 4) * 8) + } + return output +} + +// from_bytes_lowest_bits_first converts a byte array into a bitfield +// [0x0F, 0x01] => 1111 0000 1000 0000 +pub fn from_bytes_lowest_bits_first(input []byte) BitField { + mut output := new(input.len * 8) + for i, b in input { + output.field[i / 4] |= u32(b) << ((i % 4) * 8) + } + return output +} + +// from_str converts a string of characters ('0' and '1') to a bit +// array. Any character different from '0' is treated as '1'. +pub fn from_str(input string) BitField { + mut output := new(input.len) + for i in 0 .. input.len { + if input[i] != `0` { + output.set_bit(i) + } + } + return output +} + +// str converts the bit array to a string of characters ('0' and '1') and +// return the string +pub fn (input BitField) str() string { + mut output := '' + for i in 0 .. input.size { + if input.get_bit(i) == 1 { + output = output + '1' + } else { + output = output + '0' + } + } + return output +} + +// new creates an empty bit array of capable of storing 'size' bits. +pub fn new(size int) BitField { + output := BitField{ + size: size + // field: *u32(calloc(zbitnslots(size) * slot_size / 8)) + field: []u32{len: zbitnslots(size)} + } + return output +} + +// frees the memory allocated for the bitfield instance +[unsafe] +pub fn (instance &BitField) free() { + unsafe { + instance.field.free() + } +} + +// get_bit returns the value (0 or 1) of bit number 'bit_nr' (count from 0). +pub fn (instance BitField) get_bit(bitnr int) int { + if bitnr >= instance.size { + return 0 + } + return int((instance.field[bitslot(bitnr)] >> (bitnr % bitfield.slot_size)) & u32(1)) +} + +// set_bit sets bit number 'bit_nr' to 1 (count from 0). +pub fn (mut instance BitField) set_bit(bitnr int) { + if bitnr >= instance.size { + return + } + instance.field[bitslot(bitnr)] |= bitmask(bitnr) +} + +// clear_bit clears (sets to zero) bit number 'bit_nr' (count from 0). +pub fn (mut instance BitField) clear_bit(bitnr int) { + if bitnr >= instance.size { + return + } + instance.field[bitslot(bitnr)] &= ~bitmask(bitnr) +} + +// extract returns the value converted from a slice of bit numbers +// from 'start' by the length of 'len'. +// 0101 (1, 2) => 0b10 +pub fn (instance BitField) extract(start int, len int) u64 { + // panic? + if start < 0 { + return 0 + } + mut output := u64(0) + for i in 0 .. len { + output |= u64(instance.get_bit(start + len - i - 1)) << i + } + return output +} + +// insert sets bit numbers from 'start' to 'len' length with +// the value converted from the number 'value'. +// 0000 (1, 2, 0b10) => 0100 +pub fn (mut instance BitField) insert(start int, len int, _value T) { + // panic? + if start < 0 { + return + } + mut value := _value + for i in 0 .. len { + pos := start + len - i - 1 + if value & 1 == 1 { + instance.set_bit(pos) + } else { + instance.clear_bit(pos) + } + value >>= 1 + } +} + +// extract returns the value converted from a slice of bit numbers +// from 'start' by the length of 'len'. +// 0101 (1, 2) => 0b01 +pub fn (instance BitField) extract_lowest_bits_first(start int, len int) u64 { + // panic? + if start < 0 { + return 0 + } + mut output := u64(0) + for i in 0 .. len { + output |= u64(instance.get_bit(start + i)) << i + } + return output +} + +// insert sets bit numbers from 'start' to 'len' length with +// the value converted from the number 'value'. +// 0000 (1, 2, 0b10) => 0010 +pub fn (mut instance BitField) insert_lowest_bits_first(start int, len int, _value T) { + // panic? + if start < 0 { + return + } + mut value := _value + for pos in start .. start + len { + if value & 1 == 1 { + instance.set_bit(pos) + } else { + instance.clear_bit(pos) + } + value >>= 1 + } +} + +// set_all sets all bits in the array to 1. +pub fn (mut instance BitField) set_all() { + for i in 0 .. zbitnslots(instance.size) { + instance.field[i] = u32(-1) + } + instance.clear_tail() +} + +// clear_all clears (sets to zero) all bits in the array. +pub fn (mut instance BitField) clear_all() { + for i in 0 .. zbitnslots(instance.size) { + instance.field[i] = u32(0) + } +} + +// toggle_bit changes the value (from 0 to 1 or from 1 to 0) of bit +// number 'bit_nr'. +pub fn (mut instance BitField) toggle_bit(bitnr int) { + if bitnr >= instance.size { + return + } + instance.field[bitslot(bitnr)] ^= bitmask(bitnr) +} + +// bf_and performs logical AND operation on every pair of bits from 'input1' and +// 'input2' and returns the result as a new array. If inputs differ in size, +// the tail of the longer one is ignored. +pub fn bf_and(input1 BitField, input2 BitField) BitField { + size := min(input1.size, input2.size) + bitnslots := zbitnslots(size) + mut output := new(size) + for i in 0 .. bitnslots { + output.field[i] = input1.field[i] & input2.field[i] + } + output.clear_tail() + return output +} + +// bf_not toggles all bits in a bit array and returns the result as a new array. +pub fn bf_not(input BitField) BitField { + size := input.size + bitnslots := zbitnslots(size) + mut output := new(size) + for i in 0 .. bitnslots { + output.field[i] = ~input.field[i] + } + output.clear_tail() + return output +} + +// bf_or performs logical OR operation on every pair of bits from 'input1' and +// 'input2' and returns the result as a new array. If inputs differ in size, +// the tail of the longer one is ignored. +pub fn bf_or(input1 BitField, input2 BitField) BitField { + size := min(input1.size, input2.size) + bitnslots := zbitnslots(size) + mut output := new(size) + for i in 0 .. bitnslots { + output.field[i] = input1.field[i] | input2.field[i] + } + output.clear_tail() + return output +} + +// bf_xor perform logical XOR operation on every pair of bits from 'input1' and +// 'input2' and returns the result as a new array. If inputs differ in size, +// the tail of the longer one is ignored. +pub fn bf_xor(input1 BitField, input2 BitField) BitField { + size := min(input1.size, input2.size) + bitnslots := zbitnslots(size) + mut output := new(size) + for i in 0 .. bitnslots { + output.field[i] = input1.field[i] ^ input2.field[i] + } + output.clear_tail() + return output +} + +// join concatenates two bit arrays and return the result as a new array. +pub fn join(input1 BitField, input2 BitField) BitField { + output_size := input1.size + input2.size + mut output := new(output_size) + // copy the first input to output as is + for i in 0 .. zbitnslots(input1.size) { + output.field[i] = input1.field[i] + } + // find offset bit and offset slot + offset_bit := input1.size % bitfield.slot_size + offset_slot := input1.size / bitfield.slot_size + for i in 0 .. zbitnslots(input2.size) { + output.field[i + offset_slot] |= u32(input2.field[i] << u32(offset_bit)) + } + /* + * If offset_bit is not zero, additional operations are needed. + * Number of iterations depends on the nr of slots in output. Two + * options: + * (a) nr of slots in output is the sum of inputs' slots. In this + * case, the nr of bits in the last slot of output is less than the + * nr of bits in the second input (i.e. ), OR + * (b) nr of slots of output is the sum of inputs' slots less one + * (i.e. less iterations needed). In this case, the nr of bits in + * the last slot of output is greater than the nr of bits in the second + * input. + * If offset_bit is zero, no additional copies needed. + */ + if (output_size - 1) % bitfield.slot_size < (input2.size - 1) % bitfield.slot_size { + for i in 0 .. zbitnslots(input2.size) { + output.field[i + offset_slot + 1] |= u32(input2.field[i] >> u32(bitfield.slot_size - offset_bit)) + } + } else if (output_size - 1) % bitfield.slot_size > (input2.size - 1) % bitfield.slot_size { + for i in 0 .. zbitnslots(input2.size) - 1 { + output.field[i + offset_slot + 1] |= u32(input2.field[i] >> u32(bitfield.slot_size - offset_bit)) + } + } + return output +} + +// get_size returns the number of bits the array can hold. +pub fn (instance BitField) get_size() int { + return instance.size +} + +// clone creates a copy of a bit array. +pub fn (instance BitField) clone() BitField { + bitnslots := zbitnslots(instance.size) + mut output := new(instance.size) + for i in 0 .. bitnslots { + output.field[i] = instance.field[i] + } + return output +} + +// cmp compares two bit arrays bit by bit and returns 'true' if they are +// identical by length and contents and 'false' otherwise. +[deprecated: 'use a == b instead'] +[deprecated_after: '2021-06-29'] +pub fn (instance BitField) cmp(input BitField) bool { + if instance.size != input.size { + return false + } + for i in 0 .. zbitnslots(instance.size) { + if instance.field[i] != input.field[i] { + return false + } + } + return true +} + +pub fn (a BitField) == (b BitField) bool { + if a.size != b.size { + return false + } + for i in 0 .. zbitnslots(a.size) { + if a.field[i] != b.field[i] { + return false + } + } + return true +} + +// pop_count returns the number of set bits (ones) in the array. +pub fn (instance BitField) pop_count() int { + size := instance.size + bitnslots := zbitnslots(size) + tail := size % bitfield.slot_size + mut count := 0 + for i in 0 .. bitnslots - 1 { + for j in 0 .. bitfield.slot_size { + if u32(instance.field[i] >> u32(j)) & u32(1) == u32(1) { + count++ + } + } + } + for j in 0 .. tail { + if u32(instance.field[bitnslots - 1] >> u32(j)) & u32(1) == u32(1) { + count++ + } + } + return count +} + +// hamming computes the Hamming distance between two bit arrays. +pub fn hamming(input1 BitField, input2 BitField) int { + input_xored := bf_xor(input1, input2) + return input_xored.pop_count() +} + +// pos checks if the array contains a sub-array 'needle' and returns its +// position if it does, -1 if it does not, and -2 on error. +pub fn (haystack BitField) pos(needle BitField) int { + heystack_size := haystack.size + needle_size := needle.size + diff := heystack_size - needle_size + // needle longer than haystack; return error code -2 + if diff < 0 { + return -2 + } + for i := 0; i <= diff; i++ { + needle_candidate := haystack.slice(i, needle_size + i) + if needle_candidate == needle { + // needle matches a sub-array of haystack; return starting position of the sub-array + return i + } + } + // nothing matched; return -1 + return -1 +} + +// slice returns a sub-array of bits between 'start_bit_nr' (included) and +// 'end_bit_nr' (excluded). +pub fn (input BitField) slice(_start int, _end int) BitField { + // boundary checks + mut start := _start + mut end := _end + if end > input.size { + end = input.size // or panic? + } + if start > end { + start = end // or panic? + } + mut output := new(end - start) + start_offset := start % bitfield.slot_size + end_offset := (end - 1) % bitfield.slot_size + start_slot := start / bitfield.slot_size + end_slot := (end - 1) / bitfield.slot_size + output_slots := zbitnslots(end - start) + if output_slots > 1 { + if start_offset != 0 { + for i in 0 .. output_slots - 1 { + output.field[i] = u32(input.field[start_slot + i] >> u32(start_offset)) + output.field[i] = output.field[i] | u32(input.field[start_slot + i + 1] << u32(bitfield.slot_size - start_offset)) + } + } else { + for i in 0 .. output_slots - 1 { + output.field[i] = u32(input.field[start_slot + i]) + } + } + } + if start_offset > end_offset { + output.field[(end - start - 1) / bitfield.slot_size] = u32(input.field[end_slot - 1] >> u32(start_offset)) + mut mask := u32((1 << (end_offset + 1)) - 1) + mask = input.field[end_slot] & mask + mask = u32(mask << u32(bitfield.slot_size - start_offset)) + output.field[(end - start - 1) / bitfield.slot_size] |= mask + } else if start_offset == 0 { + mut mask := u32(0) + if end_offset == bitfield.slot_size - 1 { + mask = u32(-1) + } else { + mask = u32(u32(1) << u32(end_offset + 1)) + mask = mask - u32(1) + } + output.field[(end - start - 1) / bitfield.slot_size] = (input.field[end_slot] & mask) + } else { + mut mask := u32(((1 << (end_offset - start_offset + 1)) - 1) << start_offset) + mask = input.field[end_slot] & mask + mask = u32(mask >> u32(start_offset)) + output.field[(end - start - 1) / bitfield.slot_size] |= mask + } + return output +} + +// reverse reverses the order of bits in the array (swap the first with the +// last, the second with the last but one and so on). +pub fn (instance BitField) reverse() BitField { + size := instance.size + bitnslots := zbitnslots(size) + mut output := new(size) + for i := 0; i < (bitnslots - 1); i++ { + for j in 0 .. bitfield.slot_size { + if u32(instance.field[i] >> u32(j)) & u32(1) == u32(1) { + output.set_bit(size - i * bitfield.slot_size - j - 1) + } + } + } + bits_in_last_input_slot := (size - 1) % bitfield.slot_size + 1 + for j in 0 .. bits_in_last_input_slot { + if u32(instance.field[bitnslots - 1] >> u32(j)) & u32(1) == u32(1) { + output.set_bit(bits_in_last_input_slot - j - 1) + } + } + return output +} + +// resize changes the size of the bit array to 'new_size'. +pub fn (mut instance BitField) resize(new_size int) { + new_bitnslots := zbitnslots(new_size) + old_size := instance.size + old_bitnslots := zbitnslots(old_size) + mut field := []u32{len: new_bitnslots} + for i := 0; i < old_bitnslots && i < new_bitnslots; i++ { + field[i] = instance.field[i] + } + instance.field = field.clone() + instance.size = new_size + if new_size < old_size && new_size % bitfield.slot_size != 0 { + instance.clear_tail() + } +} + +// rotate circular-shifts the bits by 'offset' positions (move +// 'offset' bit to 0, 'offset+1' bit to 1, and so on). +pub fn (instance BitField) rotate(offset int) BitField { + /* + * + * This function "cuts" the bitfield into two and swaps them. + * If the offset is positive, the cutting point is counted from the + * beginning of the bit array, otherwise from the end. + * + */ + size := instance.size + // removing extra rotations + mut offset_internal := offset % size + if offset_internal == 0 { + // nothing to shift + return instance + } + if offset_internal < 0 { + offset_internal = offset_internal + size + } + first_chunk := instance.slice(0, offset_internal) + second_chunk := instance.slice(offset_internal, size) + output := join(second_chunk, first_chunk) + return output +} + +// Internal functions +// clear_tail clears the extra bits that are not part of the bitfield, but yet are allocated +fn (mut instance BitField) clear_tail() { + tail := instance.size % bitfield.slot_size + if tail != 0 { + // create a mask for the tail + mask := u32((1 << tail) - 1) + // clear the extra bits + instance.field[zbitnslots(instance.size) - 1] = instance.field[zbitnslots(instance.size) - 1] & mask + } +} + +// bitmask is the bitmask needed to access a particular bit at offset bitnr +fn bitmask(bitnr int) u32 { + return u32(u32(1) << u32(bitnr % bitfield.slot_size)) +} + +// bitslot is the slot index (i.e. the integer) where a particular bit is located +fn bitslot(size int) int { + return size / bitfield.slot_size +} + +// min returns the minimum of 2 integers; it is here to avoid importing math just for that +fn min(input1 int, input2 int) int { + if input1 < input2 { + return input1 + } else { + return input2 + } +} + +// zbitnslots returns the minimum number of whole integers, needed to represent a bitfield of size length +fn zbitnslots(length int) int { + return (length - 1) / bitfield.slot_size + 1 +} diff --git a/v_windows/v/old/vlib/bitfield/bitfield_test.v b/v_windows/v/old/vlib/bitfield/bitfield_test.v new file mode 100644 index 0000000..ae61d38 --- /dev/null +++ b/v_windows/v/old/vlib/bitfield/bitfield_test.v @@ -0,0 +1,333 @@ +import bitfield +import rand + +fn test_bf_new_size() { + instance := bitfield.new(75) + assert instance.get_size() == 75 +} + +fn test_bf_set_clear_toggle_get() { + mut instance := bitfield.new(75) + instance.set_bit(47) + assert instance.get_bit(47) == 1 + instance.clear_bit(47) + assert instance.get_bit(47) == 0 + instance.toggle_bit(47) + assert instance.get_bit(47) == 1 +} + +fn test_bf_insert_extract() { + mut instance := bitfield.new(11) + instance.set_all() + instance.insert(2, 9, 3) + assert instance.extract(2, 1) == 0 + assert instance.extract(2, 8) == 1 + assert instance.extract(10, 1) == 1 + instance.set_all() + instance.insert_lowest_bits_first(2, 9, 3) + assert instance.extract_lowest_bits_first(2, 1) == 1 + assert instance.extract_lowest_bits_first(2, 8) == 3 + assert instance.extract_lowest_bits_first(10, 1) == 0 +} + +fn test_bf_and_not_or_xor() { + len := 80 + mut input1 := bitfield.new(len) + mut input2 := bitfield.new(len) + mut i := 0 + for i < len { + if rand.intn(2) == 1 { + input1.set_bit(i) + } + if rand.intn(2) == 1 { + input2.set_bit(i) + } + i++ + } + output1 := bitfield.bf_xor(input1, input2) + bf_and := bitfield.bf_and(input1, input2) + bf_or := bitfield.bf_or(input1, input2) + bf_not := bitfield.bf_not(bf_and) + output2 := bitfield.bf_and(bf_or, bf_not) + mut result := 1 + for i < len { + if output1.get_bit(i) != output2.get_bit(i) { + result = 0 + } + } + assert result == 1 +} + +fn test_clone_cmp() { + len := 80 + mut input := bitfield.new(len) + for i in 0 .. len { + if rand.intn(2) == 1 { + input.set_bit(i) + } + } + output := input.clone() + assert output.get_size() == len + assert input == output +} + +fn test_slice_join() { + len := 80 + mut input := bitfield.new(len) + for i in 0 .. len { + if rand.intn(2) == 1 { + input.set_bit(i) + } + } + mut result := 1 + for point := 1; point < (len - 1); point++ { + // divide a bitfield into two subfields + chunk1 := input.slice(0, point) + chunk2 := input.slice(point, input.get_size()) + // concatenate them back into one and compare to the original + output := bitfield.join(chunk1, chunk2) + if input != output { + result = 0 + } + } + assert result == 1 +} + +fn test_pop_count() { + len := 80 + mut count0 := 0 + mut input := bitfield.new(len) + for i in 0 .. len { + if rand.intn(2) == 1 { + input.set_bit(i) + count0++ + } + } + count1 := input.pop_count() + assert count0 == count1 +} + +fn test_hamming() { + len := 80 + mut count := 0 + mut input1 := bitfield.new(len) + mut input2 := bitfield.new(len) + for i in 0 .. len { + match rand.intn(4) { + 0, 1 { + input1.set_bit(i) + count++ + } + 2 { + input2.set_bit(i) + count++ + } + 3 { + input1.set_bit(i) + input2.set_bit(i) + } + else {} + } + } + assert count == bitfield.hamming(input1, input2) +} + +fn test_bf_from_bytes() { + input := [byte(0x01), 0xF0, 0x0F, 0xF0, 0xFF] + output := bitfield.from_bytes(input).str() + assert output == '00000001' + '11110000' + '00001111' + '11110000' + '11111111' + newoutput := bitfield.from_str(output).str() + assert newoutput == output +} + +fn test_bf_from_bytes_lowest_bits_first() { + input := [byte(0x01), 0xF0] + output := bitfield.from_bytes_lowest_bits_first(input).str() + assert output == '10000000' + '00001111' + newoutput := bitfield.from_str(output).str() + assert newoutput == output +} + +fn test_bf_from_str() { + len := 80 + mut input := '' + for _ in 0 .. len { + if rand.intn(2) == 1 { + input = input + '1' + } else { + input = input + '0' + } + } + output := bitfield.from_str(input) + mut result := 1 + for i in 0 .. len { + if input[i] != output.get_bit(i) + 48 { + result = 0 + } + } + assert result == 1 +} + +fn test_bf_bf2str() { + len := 80 + mut input := bitfield.new(len) + for i in 0 .. len { + if rand.intn(2) == 1 { + input.set_bit(i) + } + } + mut check := '' + for i in 0 .. len { + if input.get_bit(i) == 1 { + check = check + '1' + } else { + check = check + '0' + } + } + output := input.str() + mut result := 1 + for i in 0 .. len { + if check[i] != output[i] { + result = 0 + } + } + assert result == 1 +} + +fn test_bf_set_all() { + len := 80 + mut input := bitfield.new(len) + input.set_all() + mut result := 1 + for i in 0 .. len { + if input.get_bit(i) != 1 { + result = 0 + } + } + assert result == 1 +} + +fn test_bf_clear_all() { + len := 80 + mut input := bitfield.new(len) + for i in 0 .. len { + if rand.intn(2) == 1 { + input.set_bit(i) + } + } + input.clear_all() + mut result := 1 + for i in 0 .. len { + if input.get_bit(i) != 0 { + result = 0 + } + } + assert result == 1 +} + +fn test_bf_reverse() { + len := 80 + mut input := bitfield.new(len) + for i in 0 .. len { + if rand.intn(2) == 1 { + input.set_bit(i) + } + } + check := input.clone() + output := input.reverse() + mut result := 1 + for i in 0 .. len { + if output.get_bit(i) != check.get_bit(len - i - 1) { + result = 0 + } + } + assert result == 1 +} + +fn test_bf_resize() { + len := 80 + mut input := bitfield.new(rand.intn(len) + 1) + for _ in 0 .. 100 { + input.resize(rand.intn(len) + 1) + input.set_bit(input.get_size() - 1) + } + assert input.get_bit(input.get_size() - 1) == 1 +} + +fn test_bf_pos() { + /* + * + * set haystack size to 80 + * test different sizes of needle, from 1 to 80 + * test different positions of needle, from 0 to where it fits + * all haystacks here contain exactly one instanse of needle, + * so search should return non-negative-values + * + */ + len := 80 + mut result := 1 + for i := 1; i < len; i++ { // needle size + for j in 0 .. len - i { // needle position in the haystack + // create the needle + mut needle := bitfield.new(i) + // fill the needle with random values + for k in 0 .. i { + if rand.intn(2) == 1 { + needle.set_bit(k) + } + } + // make sure the needle contains at least one set bit, selected randomly + r := rand.intn(i) + needle.set_bit(r) + // create the haystack, make sure it contains the needle + mut haystack := needle.clone() + // if there is space between the start of the haystack and the sought needle, fill it with zeroes + if j > 0 { + start := bitfield.new(j) + tmp := bitfield.join(start, haystack) + haystack = tmp + } + // if there is space between the sought needle and the end of haystack, fill it with zeroes + if j + i < len { + end := bitfield.new(len - j - i) + tmp2 := bitfield.join(haystack, end) + haystack = tmp2 + } + // now let's test + // the result should be equal to j + if haystack.pos(needle) != j { + result = 0 + } + } + } + assert result == 1 +} + +fn test_bf_rotate() { + mut result := 1 + len := 80 + for i := 1; i < 80 && result == 1; i++ { + mut chunk1 := bitfield.new(i) + chunk2 := bitfield.new(len - i) + chunk1.set_all() + input := bitfield.join(chunk1, chunk2) + output := input.rotate(i) + if output.get_bit(len - i - 1) != 0 || output.get_bit(len - i) != 1 { + result = 0 + } + } + assert result == 1 +} + +fn test_bf_printing() { + len := 80 + mut input := bitfield.new(len) + for i in 0 .. len { + if rand.intn(2) == 0 { + input.set_bit(i) + } + } + // the following should convert the bitfield input into a string automatically + println(input) + assert true +} -- cgit v1.2.3