From 9f786b6af7bead1c60ed5e497dfc0a6fc0bc2930 Mon Sep 17 00:00:00 2001 From: Augustin Cavalier Date: Tue, 09 Dec 2025 15:41:47 -0500 Subject: [PATCH] Rename "headers/private/utils" to "util". This undoes some changes from cf930b7e6c1ec2b0fef6815a3cf1a5f1d6652c9d. Nearly all the other utility directories in the tree are named "util" not "utils", so let's be consistent. --- headers/private/util/BitUtils.h | 140 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ headers/private/utils/BitUtils.h | 140 -------------------------------------------------------------------------------- src/libs/compat/freebsd_network/malloc.cpp | 2 +- src/system/kernel/util/Bitmap.cpp | 2 +- src/system/kernel/vm/vm.cpp | 3 +-- src/add-ons/input_server/devices/mouse/movement_maker.cpp | 2 +- src/add-ons/kernel/file_systems/ramfs/DataContainer.cpp | 3 +-- src/system/kernel/arch/x86/arch_cpu.cpp | 3 +-- src/add-ons/kernel/busses/scsi/ahci/ahci_controller.cpp | 3 +-- 9 files changed, 147 insertions(+), 151 deletions(-) diff --git a/headers/private/util/BitUtils.h b/headers/private/util/BitUtils.h new file mode 100644 index 0000000..ed092ca 100644 --- /dev/null +++ b/headers/private/util/BitUtils.h @@ -1,0 +1,140 @@ +/* + * Copyright 2013 Haiku, Inc. All rights reserved. + * Distributed under the terms of the MIT License. + * + * Authors: + * Paweł Dziepak, pdziepak@quarnos.org + */ +#ifndef KERNEL_UTIL_BITUTIL_H +#define KERNEL_UTIL_BITUTIL_H + + +#include + +#include + + +// http://graphics.stanford.edu/~seander/bithacks.html +static inline uint32 +next_power_of_2(uint32 v) +{ + v--; + v |= v >> 1; + v |= v >> 2; + v |= v >> 4; + v |= v >> 8; + v |= v >> 16; + v++; + + return v; +} + + +// http://graphics.stanford.edu/~seander/bithacks.html +static inline uint32 +count_set_bits(uint32 v) +{ + v = v - ((v >> 1) & 0x55555555); + v = (v & 0x33333333) + ((v >> 2) & 0x33333333); + return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; +} + + +static inline uint32 +fls(uint32 value) +{ + if (value == 0) + return 0; + +#if __has_builtin(__builtin_clz) + return ((sizeof(value) * 8) - __builtin_clz(value)); +#else + // https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog + static const uint32 masks[] = { + 0xaaaaaaaa, + 0xcccccccc, + 0xf0f0f0f0, + 0xff00ff00, + 0xffff0000 + }; + uint32 result = (value & masks[0]) != 0; + for (int i = 4; i > 0; i--) + result |= ((value & masks[i]) != 0) << i; + return result + 1; +#endif +} + + +static inline uint32 +log2(uint32 v) +{ + static const int MultiplyDeBruijnBitPosition[32] = { + 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, + 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 + }; + + v |= v >> 1; + v |= v >> 2; + v |= v >> 4; + v |= v >> 8; + v |= v >> 16; + + return MultiplyDeBruijnBitPosition[(uint32)(v * 0x07C4ACDDU) >> 27]; +} + + +template +void +bitmap_shift(T* bits, size_t bitCount, ssize_t shift) +{ + if (shift == 0) + return; + + const size_t bitsPerElement = sizeof(T) * 8; + const size_t elementsCount = (bitCount + bitsPerElement - 1) / bitsPerElement; + const size_t absoluteShift = (shift > 0) ? shift : -shift; + const size_t nElements = absoluteShift / bitsPerElement; + const size_t nBits = absoluteShift % bitsPerElement; + if (nElements != 0) { + if (shift > 0) { + // "Left" shift. + memmove(&bits[nElements], bits, sizeof(T) * (elementsCount - nElements)); + memset(bits, 0, sizeof(T) * nElements); + } else if (shift < 0) { + // "Right" shift. + memmove(bits, &bits[nElements], sizeof(T) * (elementsCount - nElements)); + memset(&bits[elementsCount - nElements], 0, sizeof(T) * nElements); + } + } + + // If the shift was by a multiple of the element size, nothing more to do. + if (nBits == 0) + return; + + // One set of bits comes from the "current" element and are shifted in the + // direction of the shift; the other set comes from the next-processed + // element and are shifted in the opposite direction. + if (shift > 0) { + // "Left" shift. + for (ssize_t i = elementsCount - 1; i >= 0; i--) { + T low = 0; + if (i != 0) + low = bits[i - 1] >> (bitsPerElement - nBits); + const T high = bits[i] << nBits; + bits[i] = low | high; + } + } else if (shift < 0) { + // "Right" shift. + for (size_t i = 0; i < elementsCount; i++) { + const T low = bits[i] >> nBits; + T high = 0; + if (i != (elementsCount - 1)) + high = bits[i + 1] << (bitsPerElement - nBits); + bits[i] = low | high; + } + } +} + + +#endif // KERNEL_UTIL_BITUTIL_H + diff --git a/headers/private/utils/BitUtils.h b/headers/private/utils/BitUtils.h deleted file mode 100644 index ed092ca..0000000 100644 --- a/headers/private/utils/BitUtils.h +++ /dev/null @@ -1,140 +1,0 @@ -/* - * Copyright 2013 Haiku, Inc. All rights reserved. - * Distributed under the terms of the MIT License. - * - * Authors: - * Paweł Dziepak, pdziepak@quarnos.org - */ -#ifndef KERNEL_UTIL_BITUTIL_H -#define KERNEL_UTIL_BITUTIL_H - - -#include - -#include - - -// http://graphics.stanford.edu/~seander/bithacks.html -static inline uint32 -next_power_of_2(uint32 v) -{ - v--; - v |= v >> 1; - v |= v >> 2; - v |= v >> 4; - v |= v >> 8; - v |= v >> 16; - v++; - - return v; -} - - -// http://graphics.stanford.edu/~seander/bithacks.html -static inline uint32 -count_set_bits(uint32 v) -{ - v = v - ((v >> 1) & 0x55555555); - v = (v & 0x33333333) + ((v >> 2) & 0x33333333); - return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; -} - - -static inline uint32 -fls(uint32 value) -{ - if (value == 0) - return 0; - -#if __has_builtin(__builtin_clz) - return ((sizeof(value) * 8) - __builtin_clz(value)); -#else - // https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog - static const uint32 masks[] = { - 0xaaaaaaaa, - 0xcccccccc, - 0xf0f0f0f0, - 0xff00ff00, - 0xffff0000 - }; - uint32 result = (value & masks[0]) != 0; - for (int i = 4; i > 0; i--) - result |= ((value & masks[i]) != 0) << i; - return result + 1; -#endif -} - - -static inline uint32 -log2(uint32 v) -{ - static const int MultiplyDeBruijnBitPosition[32] = { - 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, - 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 - }; - - v |= v >> 1; - v |= v >> 2; - v |= v >> 4; - v |= v >> 8; - v |= v >> 16; - - return MultiplyDeBruijnBitPosition[(uint32)(v * 0x07C4ACDDU) >> 27]; -} - - -template -void -bitmap_shift(T* bits, size_t bitCount, ssize_t shift) -{ - if (shift == 0) - return; - - const size_t bitsPerElement = sizeof(T) * 8; - const size_t elementsCount = (bitCount + bitsPerElement - 1) / bitsPerElement; - const size_t absoluteShift = (shift > 0) ? shift : -shift; - const size_t nElements = absoluteShift / bitsPerElement; - const size_t nBits = absoluteShift % bitsPerElement; - if (nElements != 0) { - if (shift > 0) { - // "Left" shift. - memmove(&bits[nElements], bits, sizeof(T) * (elementsCount - nElements)); - memset(bits, 0, sizeof(T) * nElements); - } else if (shift < 0) { - // "Right" shift. - memmove(bits, &bits[nElements], sizeof(T) * (elementsCount - nElements)); - memset(&bits[elementsCount - nElements], 0, sizeof(T) * nElements); - } - } - - // If the shift was by a multiple of the element size, nothing more to do. - if (nBits == 0) - return; - - // One set of bits comes from the "current" element and are shifted in the - // direction of the shift; the other set comes from the next-processed - // element and are shifted in the opposite direction. - if (shift > 0) { - // "Left" shift. - for (ssize_t i = elementsCount - 1; i >= 0; i--) { - T low = 0; - if (i != 0) - low = bits[i - 1] >> (bitsPerElement - nBits); - const T high = bits[i] << nBits; - bits[i] = low | high; - } - } else if (shift < 0) { - // "Right" shift. - for (size_t i = 0; i < elementsCount; i++) { - const T low = bits[i] >> nBits; - T high = 0; - if (i != (elementsCount - 1)) - high = bits[i + 1] << (bitsPerElement - nBits); - bits[i] = low | high; - } - } -} - - -#endif // KERNEL_UTIL_BITUTIL_H - diff --git a/src/libs/compat/freebsd_network/malloc.cpp b/src/libs/compat/freebsd_network/malloc.cpp index 54e4a11..c64deee 100644 --- a/src/libs/compat/freebsd_network/malloc.cpp +++ b/src/libs/compat/freebsd_network/malloc.cpp @@ -11,7 +11,7 @@ #include #include -#include +#include #include #include diff --git a/src/system/kernel/util/Bitmap.cpp b/src/system/kernel/util/Bitmap.cpp index 5485cb6..0a11af9 100644 --- a/src/system/kernel/util/Bitmap.cpp +++ b/src/system/kernel/util/Bitmap.cpp @@ -11,7 +11,7 @@ #include #include -#include +#include namespace BKernel { diff --git a/src/system/kernel/vm/vm.cpp b/src/system/kernel/vm/vm.cpp index 24fe6ae..d88ccad 100644 --- a/src/system/kernel/vm/vm.cpp +++ b/src/system/kernel/vm/vm.cpp @@ -47,14 +47,13 @@ #include #include #include +#include #include #include #include #include #include #include - -#include #include "VMAddressSpaceLocking.h" #include "VMAnonymousCache.h" diff --git a/src/add-ons/input_server/devices/mouse/movement_maker.cpp b/src/add-ons/input_server/devices/mouse/movement_maker.cpp index e7739dd..f101071 100644 --- a/src/add-ons/input_server/devices/mouse/movement_maker.cpp +++ b/src/add-ons/input_server/devices/mouse/movement_maker.cpp @@ -23,7 +23,7 @@ #include #include -#include +#include //#define TRACE_MOVEMENT_MAKER diff --git a/src/add-ons/kernel/file_systems/ramfs/DataContainer.cpp b/src/add-ons/kernel/file_systems/ramfs/DataContainer.cpp index 3ec34fb..6d34268 100644 --- a/src/add-ons/kernel/file_systems/ramfs/DataContainer.cpp +++ b/src/add-ons/kernel/file_systems/ramfs/DataContainer.cpp @@ -8,11 +8,10 @@ #include #include +#include #include #include #include - -#include #include #include diff --git a/src/system/kernel/arch/x86/arch_cpu.cpp b/src/system/kernel/arch/x86/arch_cpu.cpp index 1fc5eaf..c9fea50 100644 --- a/src/system/kernel/arch/x86/arch_cpu.cpp +++ b/src/system/kernel/arch/x86/arch_cpu.cpp @@ -26,11 +26,10 @@ #include #include #include +#include #include #include #include - -#include #include #include diff --git a/src/add-ons/kernel/busses/scsi/ahci/ahci_controller.cpp b/src/add-ons/kernel/busses/scsi/ahci/ahci_controller.cpp index 63d5697..0bd81b0 100644 --- a/src/add-ons/kernel/busses/scsi/ahci/ahci_controller.cpp +++ b/src/add-ons/kernel/busses/scsi/ahci/ahci_controller.cpp @@ -11,8 +11,7 @@ #include #include #include - -#include +#include #define TRACE(a...) dprintf("ahci: " a) #define FLOW(a...) dprintf("ahci: " a) -- gitore 0.2.3