This should really go into upstream ddlog, but it's OK here for the moment.
Signed-off-by: Ben Pfaff <[email protected]> --- northd/automake.mk | 4 +- northd/bitwise.dl | 272 +++++++++++++++++++++++++++++++++++++++++++++ northd/bitwise.rs | 133 ++++++++++++++++++++++ northd/ovn.dl | 5 +- northd/ovn.rs | 5 - 5 files changed, 409 insertions(+), 10 deletions(-) create mode 100644 northd/bitwise.dl create mode 100644 northd/bitwise.rs diff --git a/northd/automake.mk b/northd/automake.mk index d64d1d197c77..aaea7e1b1336 100644 --- a/northd/automake.mk +++ b/northd/automake.mk @@ -17,6 +17,7 @@ EXTRA_DIST += \ northd/ovn-sb.dlopts \ northd/ovn.toml \ northd/ovn.rs \ + northd/bitwise.rs \ northd/ovsdb2ddlog2c \ $(ddlog_sources) @@ -28,7 +29,8 @@ ddlog_sources = \ northd/multicast.dl \ northd/ovn.dl \ northd/ovn.rs \ - northd/helpers.dl + northd/helpers.dl \ + northd/bitwise.dl ddlog_nodist_sources = \ northd/OVN_Northbound.dl \ northd/OVN_Southbound.dl diff --git a/northd/bitwise.dl b/northd/bitwise.dl new file mode 100644 index 000000000000..877d155a2304 --- /dev/null +++ b/northd/bitwise.dl @@ -0,0 +1,272 @@ +/* + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/* + * Returns true if and only if 'x' is a power of 2. + */ +function is_power_of_two(x: u8): bool { x != 0 and (x & (x - 1)) == 0 } +function is_power_of_two(x: u16): bool { x != 0 and (x & (x - 1)) == 0 } +function is_power_of_two(x: u32): bool { x != 0 and (x & (x - 1)) == 0 } +function is_power_of_two(x: u64): bool { x != 0 and (x & (x - 1)) == 0 } +function is_power_of_two(x: u128): bool { x != 0 and (x & (x - 1)) == 0 } + +/* + * Returns the next power of 2 greater than 'x', or None if that's bigger than the + * type's maximum value. + */ +function next_power_of_two(x: u8): Option<u8> { u8_next_power_of_two(x) } +function next_power_of_two(x: u16): Option<u16> { u16_next_power_of_two(x) } +function next_power_of_two(x: u32): Option<u32> { u32_next_power_of_two(x) } +function next_power_of_two(x: u64): Option<u64> { u64_next_power_of_two(x) } +function next_power_of_two(x: u128): Option<u128> { u128_next_power_of_two(x) } + +extern function u8_next_power_of_two(x: u8): Option<u8> +extern function u16_next_power_of_two(x: u16): Option<u16> +extern function u32_next_power_of_two(x: u32): Option<u32> +extern function u64_next_power_of_two(x: u64): Option<u64> +extern function u128_next_power_of_two(x: u128): Option<u128> + +/* + * Returns the next power of 2 greater than 'x', or 0 if that's bigger than the + * type's maximum value. + */ +function wrapping_next_power_of_two(x: u8): u8 { u8_wrapping_next_power_of_two(x) } +function wrapping_next_power_of_two(x: u16): u16 { u16_wrapping_next_power_of_two(x) } +function wrapping_next_power_of_two(x: u32): u32 { u32_wrapping_next_power_of_two(x) } +function wrapping_next_power_of_two(x: u64): u64 { u64_wrapping_next_power_of_two(x) } +function wrapping_next_power_of_two(x: u128): u128 { u128_wrapping_next_power_of_two(x) } + +extern function u8_wrapping_next_power_of_two(x: u8): u8 +extern function u16_wrapping_next_power_of_two(x: u16): u16 +extern function u32_wrapping_next_power_of_two(x: u32): u32 +extern function u64_wrapping_next_power_of_two(x: u64): u64 +extern function u128_wrapping_next_power_of_two(x: u128): u128 + +/* + * Number of 1-bits in the binary representation of 'x'. + */ +function count_ones(x: u8): u32 { u8_count_ones(x) } +function count_ones(x: u16): u32 { u16_count_ones(x) } +function count_ones(x: u32): u32 { u32_count_ones(x) } +function count_ones(x: u64): u32 { u64_count_ones(x) } +function count_ones(x: u128): u32 { u128_count_ones(x) } + +extern function u8_count_ones(x: u8): u32 +extern function u16_count_ones(x: u16): u32 +extern function u32_count_ones(x: u32): u32 +extern function u64_count_ones(x: u64): u32 +extern function u128_count_ones(x: u128): u32 + +/* + * Number of 0-bits in the binary representation of 'x'. + */ +function count_zeros(x: u8): u32 { u8_count_zeros(x) } +function count_zeros(x: u16): u32 { u16_count_zeros(x) } +function count_zeros(x: u32): u32 { u32_count_zeros(x) } +function count_zeros(x: u64): u32 { u64_count_zeros(x) } +function count_zeros(x: u128): u32 { u128_count_zeros(x) } + +extern function u8_count_zeros(x: u8): u32 +extern function u16_count_zeros(x: u16): u32 +extern function u32_count_zeros(x: u32): u32 +extern function u64_count_zeros(x: u64): u32 +extern function u128_count_zeros(x: u128): u32 + +/* + * Number of leading 0-bits in the binary representation of 'x'. + */ +function leading_zeros(x: u8): u32 { u8_leading_zeros(x) } +function leading_zeros(x: u16): u32 { u16_leading_zeros(x) } +function leading_zeros(x: u32): u32 { u32_leading_zeros(x) } +function leading_zeros(x: u64): u32 { u64_leading_zeros(x) } +function leading_zeros(x: u128): u32 { u128_leading_zeros(x) } + +extern function u8_leading_zeros(x: u8): u32 +extern function u16_leading_zeros(x: u16): u32 +extern function u32_leading_zeros(x: u32): u32 +extern function u64_leading_zeros(x: u64): u32 +extern function u128_leading_zeros(x: u128): u32 + +/* + * Number of leading 1-bits in the binary representation of 'x'. + */ +function leading_ones(x: u8): u32 { u8_leading_ones(x) } +function leading_ones(x: u16): u32 { u16_leading_ones(x) } +function leading_ones(x: u32): u32 { u32_leading_ones(x) } +function leading_ones(x: u64): u32 { u64_leading_ones(x) } +function leading_ones(x: u128): u32 { u128_leading_ones(x) } + +extern function u8_leading_ones(x: u8): u32 +extern function u16_leading_ones(x: u16): u32 +extern function u32_leading_ones(x: u32): u32 +extern function u64_leading_ones(x: u64): u32 +extern function u128_leading_ones(x: u128): u32 + +/* + * Number of trailing 0-bits in the binary representation of 'x'. + */ +function trailing_zeros(x: u8): u32 { u8_trailing_zeros(x) } +function trailing_zeros(x: u16): u32 { u16_trailing_zeros(x) } +function trailing_zeros(x: u32): u32 { u32_trailing_zeros(x) } +function trailing_zeros(x: u64): u32 { u64_trailing_zeros(x) } +function trailing_zeros(x: u128): u32 { u128_trailing_zeros(x) } + +extern function u8_trailing_zeros(x: u8): u32 +extern function u16_trailing_zeros(x: u16): u32 +extern function u32_trailing_zeros(x: u32): u32 +extern function u64_trailing_zeros(x: u64): u32 +extern function u128_trailing_zeros(x: u128): u32 + +/* + * Number of trailing 0-bits in the binary representation of 'x'. + */ +function trailing_ones(x: u8): u32 { u8_trailing_ones(x) } +function trailing_ones(x: u16): u32 { u16_trailing_ones(x) } +function trailing_ones(x: u32): u32 { u32_trailing_ones(x) } +function trailing_ones(x: u64): u32 { u64_trailing_ones(x) } +function trailing_ones(x: u128): u32 { u128_trailing_ones(x) } + +extern function u8_trailing_ones(x: u8): u32 +extern function u16_trailing_ones(x: u16): u32 +extern function u32_trailing_ones(x: u32): u32 +extern function u64_trailing_ones(x: u64): u32 +extern function u128_trailing_ones(x: u128): u32 + +/* + * Reverses the order of bits in 'x'. + */ +function reverse_bits(x: u8): u8 { u8_reverse_bits(x) } +function reverse_bits(x: u16): u16 { u16_reverse_bits(x) } +function reverse_bits(x: u32): u32 { u32_reverse_bits(x) } +function reverse_bits(x: u64): u64 { u64_reverse_bits(x) } +function reverse_bits(x: u128): u128 { u128_reverse_bits(x) } + +extern function u8_reverse_bits(x: u8): u8 +extern function u16_reverse_bits(x: u16): u16 +extern function u32_reverse_bits(x: u32): u32 +extern function u64_reverse_bits(x: u64): u64 +extern function u128_reverse_bits(x: u128): u128 + +/* + * Reverses the order of bytes in 'x'. + */ +function swap_bytes(x: u8): u8 { u8_swap_bytes(x) } +function swap_bytes(x: u16): u16 { u16_swap_bytes(x) } +function swap_bytes(x: u32): u32 { u32_swap_bytes(x) } +function swap_bytes(x: u64): u64 { u64_swap_bytes(x) } +function swap_bytes(x: u128): u128 { u128_swap_bytes(x) } + +extern function u8_swap_bytes(x: u8): u8 +extern function u16_swap_bytes(x: u16): u16 +extern function u32_swap_bytes(x: u32): u32 +extern function u64_swap_bytes(x: u64): u64 +extern function u128_swap_bytes(x: u128): u128 + +/* + * Converts 'x' from big endian to the machine's native endianness. + * On a big-endian machine it is a no-op. + * On a little-end machine it is equivalent to swap_bytes(). + */ +function from_be(x: u8): u8 { u8_from_be(x) } +function from_be(x: u16): u16 { u16_from_be(x) } +function from_be(x: u32): u32 { u32_from_be(x) } +function from_be(x: u64): u64 { u64_from_be(x) } +function from_be(x: u128): u128 { u128_from_be(x) } + +extern function u8_from_be(x: u8): u8 +extern function u16_from_be(x: u16): u16 +extern function u32_from_be(x: u32): u32 +extern function u64_from_be(x: u64): u64 +extern function u128_from_be(x: u128): u128 + +/* + * Converts 'x' from the machine's native endianness to big endian. + * On a big-endian machine it is a no-op. + * On a little-endian machine it is equivalent to swap_bytes(). + */ +function to_be(x: u8): u8 { u8_to_be(x) } +function to_be(x: u16): u16 { u16_to_be(x) } +function to_be(x: u32): u32 { u32_to_be(x) } +function to_be(x: u64): u64 { u64_to_be(x) } +function to_be(x: u128): u128 { u128_to_be(x) } + +extern function u8_to_be(x: u8): u8 +extern function u16_to_be(x: u16): u16 +extern function u32_to_be(x: u32): u32 +extern function u64_to_be(x: u64): u64 +extern function u128_to_be(x: u128): u128 + +/* + * Converts 'x' from little endian to the machine's native endianness. + * On a little-endian machine it is a no-op. + * On a big-endian machine it is equivalent to swap_bytes(). + */ +function from_le(x: u8): u8 { u8_from_le(x) } +function from_le(x: u16): u16 { u16_from_le(x) } +function from_le(x: u32): u32 { u32_from_le(x) } +function from_le(x: u64): u64 { u64_from_le(x) } +function from_le(x: u128): u128 { u128_from_le(x) } + +extern function u8_from_le(x: u8): u8 +extern function u16_from_le(x: u16): u16 +extern function u32_from_le(x: u32): u32 +extern function u64_from_le(x: u64): u64 +extern function u128_from_le(x: u128): u128 + +/* + * Converts 'x' from the machine's native endianness to little endian. + * On a little-endian machine it is a no-op. + * On a big-endian machine it is equivalent to swap_bytes(). + */ +function to_le(x: u8): u8 { u8_to_le(x) } +function to_le(x: u16): u16 { u16_to_le(x) } +function to_le(x: u32): u32 { u32_to_le(x) } +function to_le(x: u64): u64 { u64_to_le(x) } +function to_le(x: u128): u128 { u128_to_le(x) } + +extern function u8_to_le(x: u8): u8 +extern function u16_to_le(x: u16): u16 +extern function u32_to_le(x: u32): u32 +extern function u64_to_le(x: u64): u64 +extern function u128_to_le(x: u128): u128 + +/* + * Rotates the bits in 'x' left by 'n' positions. + */ +function rotate_left(x: u8, n: u32): u8 { u8_rotate_left(x, n) } +function rotate_left(x: u16, n: u32): u16 { u16_rotate_left(x, n) } +function rotate_left(x: u32, n: u32): u32 { u32_rotate_left(x, n) } +function rotate_left(x: u64, n: u32): u64 { u64_rotate_left(x, n) } +function rotate_left(x: u128, n: u32): u128 { u128_rotate_left(x, n) } + +extern function u8_rotate_left(x: u8, n: u32): u8 +extern function u16_rotate_left(x: u16, n: u32): u16 +extern function u32_rotate_left(x: u32, n: u32): u32 +extern function u64_rotate_left(x: u64, n: u32): u64 +extern function u128_rotate_left(x: u128, n: u32): u128 + +/* + * Rotates the bits in 'x' right by 'n' positions. + */ +function rotate_right(x: u8, n: u32): u8 { u8_rotate_right(x, n) } +function rotate_right(x: u16, n: u32): u16 { u16_rotate_right(x, n) } +function rotate_right(x: u32, n: u32): u32 { u32_rotate_right(x, n) } +function rotate_right(x: u64, n: u32): u64 { u64_rotate_right(x, n) } +function rotate_right(x: u128, n: u32): u128 { u128_rotate_right(x, n) } + +extern function u8_rotate_right(x: u8, n: u32): u8 +extern function u16_rotate_right(x: u16, n: u32): u16 +extern function u32_rotate_right(x: u32, n: u32): u32 +extern function u64_rotate_right(x: u64, n: u32): u64 +extern function u128_rotate_right(x: u128, n: u32): u128 diff --git a/northd/bitwise.rs b/northd/bitwise.rs new file mode 100644 index 000000000000..97c0ecfa3632 --- /dev/null +++ b/northd/bitwise.rs @@ -0,0 +1,133 @@ +/* + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +use ddlog_std::option2std; + +pub fn u8_next_power_of_two(x: &u8) -> ddlog_std::Option<u8> { + option2std(x.checked_next_power_of_two()) +} +pub fn u16_next_power_of_two(x: &u16) -> ddlog_std::Option<u16> { + option2std(x.checked_next_power_of_two()) +} +pub fn u32_next_power_of_two(x: &u32) -> ddlog_std::Option<u32> { + option2std(x.checked_next_power_of_two()) +} +pub fn u64_next_power_of_two(x: &u64) -> ddlog_std::Option<u64> { + option2std(x.checked_next_power_of_two()) +} +pub fn u128_next_power_of_two(x: &u128) -> ddlog_std::Option<u128> { + option2std(x.checked_next_power_of_two()) +} + +// Rust has wrapping_next_power_of_two() in nightly. We implement it +// ourselves to avoid the dependency. +pub fn u8_wrapping_next_power_of_two(x: &u8) -> u8 { + x.checked_next_power_of_two().unwrap_or(0) +} +pub fn u16_wrapping_next_power_of_two(x: &u16) -> u16 { + x.checked_next_power_of_two().unwrap_or(0) +} +pub fn u32_wrapping_next_power_of_two(x: &u32) -> u32 { + x.checked_next_power_of_two().unwrap_or(0) +} +pub fn u64_wrapping_next_power_of_two(x: &u64) -> u64 { + x.checked_next_power_of_two().unwrap_or(0) +} +pub fn u128_wrapping_next_power_of_two(x: &u128) -> u128 { + x.checked_next_power_of_two().unwrap_or(0) +} + +pub fn u8_count_ones(x: &u8) -> u32 { x.count_ones() } +pub fn u16_count_ones(x: &u16) -> u32 { x.count_ones() } +pub fn u32_count_ones(x: &u32) -> u32 { x.count_ones() } +pub fn u64_count_ones(x: &u64) -> u32 { x.count_ones() } +pub fn u128_count_ones(x: &u128) -> u32 { x.count_ones() } + +pub fn u8_count_zeros(x: &u8) -> u32 { x.count_zeros() } +pub fn u16_count_zeros(x: &u16) -> u32 { x.count_zeros() } +pub fn u32_count_zeros(x: &u32) -> u32 { x.count_zeros() } +pub fn u64_count_zeros(x: &u64) -> u32 { x.count_zeros() } +pub fn u128_count_zeros(x: &u128) -> u32 { x.count_zeros() } + +pub fn u8_leading_ones(x: &u8) -> u32 { x.leading_ones() } +pub fn u16_leading_ones(x: &u16) -> u32 { x.leading_ones() } +pub fn u32_leading_ones(x: &u32) -> u32 { x.leading_ones() } +pub fn u64_leading_ones(x: &u64) -> u32 { x.leading_ones() } +pub fn u128_leading_ones(x: &u128) -> u32 { x.leading_ones() } + +pub fn u8_leading_zeros(x: &u8) -> u32 { x.leading_zeros() } +pub fn u16_leading_zeros(x: &u16) -> u32 { x.leading_zeros() } +pub fn u32_leading_zeros(x: &u32) -> u32 { x.leading_zeros() } +pub fn u64_leading_zeros(x: &u64) -> u32 { x.leading_zeros() } +pub fn u128_leading_zeros(x: &u128) -> u32 { x.leading_zeros() } + +pub fn u8_trailing_ones(x: &u8) -> u32 { x.trailing_ones() } +pub fn u16_trailing_ones(x: &u16) -> u32 { x.trailing_ones() } +pub fn u32_trailing_ones(x: &u32) -> u32 { x.trailing_ones() } +pub fn u64_trailing_ones(x: &u64) -> u32 { x.trailing_ones() } +pub fn u128_trailing_ones(x: &u128) -> u32 { x.trailing_ones() } + +pub fn u8_trailing_zeros(x: &u8) -> u32 { x.trailing_zeros() } +pub fn u16_trailing_zeros(x: &u16) -> u32 { x.trailing_zeros() } +pub fn u32_trailing_zeros(x: &u32) -> u32 { x.trailing_zeros() } +pub fn u64_trailing_zeros(x: &u64) -> u32 { x.trailing_zeros() } +pub fn u128_trailing_zeros(x: &u128) -> u32 { x.trailing_zeros() } + +pub fn u8_reverse_bits(x: &u8) -> u8 { x.reverse_bits() } +pub fn u16_reverse_bits(x: &u16) -> u16 { x.reverse_bits() } +pub fn u32_reverse_bits(x: &u32) -> u32 { x.reverse_bits() } +pub fn u64_reverse_bits(x: &u64) -> u64 { x.reverse_bits() } +pub fn u128_reverse_bits(x: &u128) -> u128 { x.reverse_bits() } + +pub fn u8_swap_bytes(x: &u8) -> u8 { x.swap_bytes() } +pub fn u16_swap_bytes(x: &u16) -> u16 { x.swap_bytes() } +pub fn u32_swap_bytes(x: &u32) -> u32 { x.swap_bytes() } +pub fn u64_swap_bytes(x: &u64) -> u64 { x.swap_bytes() } +pub fn u128_swap_bytes(x: &u128) -> u128 { x.swap_bytes() } + +pub fn u8_from_be(x: &u8) -> u8 { u8::from_be(*x) } +pub fn u16_from_be(x: &u16) -> u16 { u16::from_be(*x) } +pub fn u32_from_be(x: &u32) -> u32 { u32::from_be(*x) } +pub fn u64_from_be(x: &u64) -> u64 { u64::from_be(*x) } +pub fn u128_from_be(x: &u128) -> u128 { u128::from_be(*x) } + +pub fn u8_to_be(x: &u8) -> u8 { x.to_be() } +pub fn u16_to_be(x: &u16) -> u16 { x.to_be() } +pub fn u32_to_be(x: &u32) -> u32 { x.to_be() } +pub fn u64_to_be(x: &u64) -> u64 { x.to_be() } +pub fn u128_to_be(x: &u128) -> u128 { x.to_be() } + +pub fn u8_from_le(x: &u8) -> u8 { u8::from_le(*x) } +pub fn u16_from_le(x: &u16) -> u16 { u16::from_le(*x) } +pub fn u32_from_le(x: &u32) -> u32 { u32::from_le(*x) } +pub fn u64_from_le(x: &u64) -> u64 { u64::from_le(*x) } +pub fn u128_from_le(x: &u128) -> u128 { u128::from_le(*x) } + +pub fn u8_to_le(x: &u8) -> u8 { x.to_le() } +pub fn u16_to_le(x: &u16) -> u16 { x.to_le() } +pub fn u32_to_le(x: &u32) -> u32 { x.to_le() } +pub fn u64_to_le(x: &u64) -> u64 { x.to_le() } +pub fn u128_to_le(x: &u128) -> u128 { x.to_le() } + +pub fn u8_rotate_left(x: &u8, n: &u32) -> u8 { x.rotate_left(*n) } +pub fn u16_rotate_left(x: &u16, n: &u32) -> u16 { x.rotate_left(*n) } +pub fn u32_rotate_left(x: &u32, n: &u32) -> u32 { x.rotate_left(*n) } +pub fn u64_rotate_left(x: &u64, n: &u32) -> u64 { x.rotate_left(*n) } +pub fn u128_rotate_left(x: &u128, n: &u32) -> u128 { x.rotate_left(*n) } + +pub fn u8_rotate_right(x: &u8, n: &u32) -> u8 { x.rotate_right(*n) } +pub fn u16_rotate_right(x: &u16, n: &u32) -> u16 { x.rotate_right(*n) } +pub fn u32_rotate_right(x: &u32, n: &u32) -> u32 { x.rotate_right(*n) } +pub fn u64_rotate_right(x: &u64, n: &u32) -> u64 { x.rotate_right(*n) } +pub fn u128_rotate_right(x: &u128, n: &u32) -> u128 { x.rotate_right(*n) } diff --git a/northd/ovn.dl b/northd/ovn.dl index 1e9e65d2a2b2..52fe3d82be33 100644 --- a/northd/ovn.dl +++ b/northd/ovn.dl @@ -13,7 +13,7 @@ */ import ovsdb - +import bitwise /* Logical port is enabled if it does not have an enabled flag or the flag is true */ function is_enabled(s: Option<bool>): bool = { @@ -375,9 +375,6 @@ extern function ovn_internal_version(): string */ extern function json_string_escape(s: string): string -/* Returns the number of 1-bits in `x`, between 0 and 64 inclusive */ -extern function count_1bits(x: bit<64>): bit<8> - /* For a 'key' of the form "IP:port" or just "IP", returns * (v46_ip, port) tuple. */ extern function ip_address_and_port_from_lb_key(k: string): Option<(v46_ip, bit<16>)> diff --git a/northd/ovn.rs b/northd/ovn.rs index 46a2e2d3c4d5..c4842bdbc424 100644 --- a/northd/ovn.rs +++ b/northd/ovn.rs @@ -488,11 +488,6 @@ pub fn ip_address_and_port_from_lb_key(k: &String) -> } } -pub fn count_1bits(x: &u64) -> u8 { - x.count_ones() as u8 -} - - pub fn str_to_int(s: &String, base: &u16) -> ddlog_std::Option<u64> { let mut i: raw::c_int = 0; let ok = unsafe { -- 2.29.2 _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
