dolphin icon indicating copy to clipboard operation
dolphin copied to clipboard

Published 20 hours ago • verified publisher icon dolphin-emu

Update and Re-License BitUtils.h

Open Minty-Meeo opened this issue 2 years ago • 8 comments

In preparation for PR #10846, I have updated BitUtils.h and will be attempting to re-license it under the Creative Commons Zero 1.0 public-domain-equivalent license. This header is a home to many "best practice" and/or "common sense" functions which are useful in a multitude of places across the Dolphin Emulator project. Some implementations even outright state they originate from, or can be found verbatim on sources such as the public domain https://graphics.stanford.edu/~seander/bithacks.html, http://aggregate.org/MAGIC, or http://www.open-std.org (in the case of the BitCast idiom).

I have found the following individuals to have made notable contributions to this header, and would appreciate their cooperation in this re-licensing:

@lioncash

  • BitSize
    • Common-sense implementation
    • Can subjectively be improved as a std::integral_constant
  • ExtractBit (variable)
    • Common-sense implementation
    • Added DEBUG_ASSERT, now returns bool
  • ExtractBit (constant)
    • Common-sense implementation
  • ExtractBits (variable)
    • Replaced with ExtractBitsU (new implementation)
  • ExtractBits (constant)
    • Replaced with ExtractBitsU (new implementation)
  • RotateLeft
    • To be removed with transition to C++20
  • RotateRight
    • To be removed with transition to C++20
  • BitCast
    • To be removed with transition to C++20

@jordan-woyak

  • SetBit (variable)
    • Replaced with InsertBit (new implementation)
  • SetBit (constant)
    • Replaced with InsertBit (new implementation)
  • BitCastPtrType
  • BitCastPtr
  • ExpandValue

@Techjar

  • BitCastToArray
  • BitCastFromArray

@blubberdiblub

  • IsValidLowMask

@Pokechu22

  • FlagBit
  • Flags

@merryhime

  • CountTrailingZerosConst
    • To be removed with transition to C++20
  • CountTrailingZeros (64-bit)
    • To be removed with transition to C++20
  • CountTrailingZeros (32-bit)
    • To be removed with transition to C++20

@MerryMage

  • CountLeadingZeros (64-bit)
    • To be removed with transition to C++20
  • CountLeadingZeros (32-bit)
    • To be removed with transition to C++20

Misc.

  • jordan-woyak for the probable originator of CountLeadingZeros implementation
  • @shuffle2 for further abstracting things with CountLeadingZerosConst function (moved code)
  • @Tilka for fixing C++23 deprecation in BitCast implementation
  • @tellowkrinkle and @iWeaker for minor contributions

Though not strictly necessary, it may also be worth changing BitUtilsTest.cpp to be a CC0-1.0 licensed file as well. In that case, I will also need cooperation from @spycrab and @ligfx, among other duplicate contributors.

For a more long form analysis of the history of this file, I have compiled the following:

=========================================================================

Jan 14, 2017 - lioncash - Common: Add bit utility header

  • BitSize
  • ExtractBit (variable)
  • ExtractBit (constant)
  • ExtractBits (variable)
  • ExtractBits (constant)

Jun 22, 2017 - blubberdiblub - Add function testing whether a bitmask is valid.

  • IsValidLowMask

Mar 31, 2018 - lioncache - CommonFuncs: Generify rotation functions and move them to BitUtils.h

  • RotateLeft (moved and rewritten, but common-sense implementation)
  • RotateRight (moved and rewritten, but common-sense implementation)

May 10, 2018 - lioncache - BitUtils: Add C++14/C++17 compatible equivalent of std::bit_cast from C++2a

  • BitCast (the implementation of which heavily borrows from https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0476r2.html)

Feb 2, 2019 - jordan-woyak - WiimoteEmu: Major renaming and cleanup.

  • SetBit (variable) (moved from Core/HW/WiimoteEmu/WiimoteEmu.cpp : line 1213. Originally implemented in commit 42b9392784b5aae840d818c7c4d349c184e6f035, also by jordan-woyak.)

Feb 2, 2019 - jordan-woyak - WiimoteEmu: Code cleanups.

  • BitCastPtrType
  • BitCastPtr
  • Fixed SetBit bug if sizeof(T) > sizeof(int)

Dec 22, 2019 - Techjar - Common/BitUtils: Implement BitCast(To|From)Array

  • BitCastToArray
  • BitCastFromArray

Jan 4, 2020 - Pokechu22 - Implement Broadway GPIOs

  • FlagBit
  • Flags

Feb 17, 2020 - jordan-woyak - InputCommon: Add types to ControllerEmu that represent raw controller inputs and calibration data to calculate normalized input values.

  • SetBit (constant)
  • ExpandValue

Dec 27, 2020 - MerryMage - BitUtils: Add CountLeadingZeros

  • CountLeadingZeros (64-bit)
    • __GNUC__ preprocessor blocks used __builtin_clzll (common sense)
    • _MSC_VER && _M_ARM64 preprocessor blocks used _CountLeadingZeros (common sense)
    • _MSC_VER && _M_x86_64 preprocessor blocks used an inverted _BitScanReverse64 (common sense)
    • Fallback implementation clearly more inspired by existing implementation in "Core/Common/MathUtil.h : line 157". Implementation in "Core/Common/Arm64Emitter.cpp : line 29" is similar, but un-optimal, thus discarded.
      • Core/Common/MathUtil.h's implementation of CountLeadingZeros history
        • 10d57a3402cc698cffc4bf3299113073264eb314 - Mar 5, 2013 - jordan-woyak - Use standard binary multiple unit symbols for game size display.
        • fe3a54d7fd8c85960fed04d28d5dedbc1d94845d - Mar 5, 2013 - jordan-woyak - Buildfix!
        • b34991c4c344832d92183a5cd9d7b591e99e74be - Mar 5, 2013 - jordan-woyak - Buildfix for real.
        • 2095641af0348b40befe91f4f36d81d992f822e2 - Mar 5, 2013 - jordan-woyak - OK, seriously, buildfix. I shouldn't even have commit access!
        • edd9d0e0ef6898a0528ac6389e93e9fca6132ff6 - Mar 19, 2013 - lioncash - Clean up more space/tab mismatches in AudioCommon, Common, and VideoCommon.
        • 94da4e1aa29a68cb723898a63bd01568bbbd8c4f - Feb 26, 2014 - degasus - MathUtil: Change Log2 return value to int
        • 4f02132f9323a147c68b7dc1a79a62be33c1f170 - Mar 4, 2014 - Sonicadvance1 - Make our architecture defines less stupid.
        • f69e6ef16f1d27059e524a537f0b685081091b97 - Sep 3, 2014 - lioncash - Common: Remove unnecessary define check in Log2
        • 94c20db36968bfcef67d43203ad19c4876f439d3 - Sep 8, 2014 - FioraAeterna - Rename Log2 and add IsPow2 to MathUtils for future use
        • 3570c7f03a2aa90aa634f96c0af1969af610f14d - Jun 24, 2016 - delroth - Reformat all the things. Have fun with merge conflicts.
        • e1a3e41bf33bf6a366760ede17c2e3bd2b106116 - Jun 7, 2017 - shuffle2 - fix various instances of -1 being assigned to unsigned types
      • Core/Common/Arm64Emitter.cpp's implementation of CountLeadingZeros history
        • 05b72c5d31f8c3b04744e62626594847ab1d68c2 - Jun 7, 2015 - Sonicadvance1 - [AArch64] Upstream PPSSPP's emitter changes.
        • 3570c7f03a2aa90aa634f96c0af1969af610f14d - Jun 24, 2016 - delroth - Reformat all the things. Have fun with merge conflicts.
        • 91cefe6c8a4e42498573a12fce4c6633ba4ae780 - Mar 23, 2018 - lioncash - Arm64Emitter: Make IsImmArithmetic, IsImmLogical, FPImm8ToFloat, and FPImm8FromFloat internally linked
  • CountLeadingZeros (32-bit)

Dec 28, 2020 - iWeaker authored and leoetlino committed - BitUtils: Fix uint64_t gcc compile (Linux)

  • Fixes exactly what the commit title says

Jan 3, 2021 - MerryMage - BitUtils: __builtin_clz is undefined when value == 0

  • Fixes exactly what the commit title says

Jan 10, 2021 - shuffle2 - BitUtils: initialize variables

  • Fixes exactly what the commit title says

Jan 10, 2021 - shuffle2 - BitUtils: loosen clz to inline on msvc/arm64

  • CONSTEXPR_FROM_INTRINSIC (now removed)

Jan 10, 2021 - shuffle2 - BitUtils: cleanup constexpr usage for msvc clz

  • CountLeadingZerosConst
  • Reworked CountLeadingZeros fallback method

Jul 4, 2021 - delroth - treewide: convert GPLv2+ license info to SPDX tags

  • Fixes exactly what the commit title says

Jul 10, 2021 - JosJuice - JitArm64: Turn IsImmLogical into a constexpr constructor

  • LargestPowerOf2Divisor (tweaked and moved from Arm64Emitter.cpp) (now removed)
    • Core/Common/Arm64Emitter.cpp's implementation history
      • 05b72c5d31f8c3b04744e62626594847ab1d68c2 - Jun 7, 2015 - Sonicadvance1 - [AArch64] Upstream PPSSPP's emitter changes.
      • 91cefe6c8a4e42498573a12fce4c6633ba4ae780 - Mar 23, 2018 - lioncash - Arm64Emitter: Make IsImmArithmetic, IsImmLogical, FPImm8ToFloat, and FPImm8FromFloat internally linked

Jun 12, 2022 - Tilka - Common: replace std::aligned_storage_t with alignas

  • Modifies BitCast

Jul 10, 2022 - merryhime - BitUtils: Implement CountTrailingZeros

  • CountTrailingZerosConst
  • CountTrailingZeros (64-bit)
  • CountTrailingZeros (32-bit)

Jul 10, 2022 - tellowkrinkle - Common: Fix CountTrailingZeros for weird compilers

  • Modifies CountTrailingZeros (32-bit)

Aug 5, 2022 - JosJuice - Common: Remove unused stuff from BitUtils.h

  • Removes LargestPowerOf2Divisor

Minty-Meeo avatar Oct 07 '22 02:10 Minty-Meeo

Forgive me of any potential ignorance, but you don't seem to state why you want to do this relicense? What are your reasons for wanting to do this?

MayImilae avatar Oct 07 '22 02:10 MayImilae

@MayImilae - they talk about it in 10846 . They want to license their new code outside of Dolphin's GPL (so others don't have to be shackled by the GPL) but they rely on Dolphin common-code so they want to relicense that code so their code can be licensed as desired.

iwubcode avatar Oct 07 '22 02:10 iwubcode

Yep. My apologies for forgetting to mention the reason for this call to action. Neobrain convinced me to license BitFieldView.h under BSD 3-clause, while Merryhime rightly convinced me to lean on Dolphin's common libraries for certain functionalities. It didn't sit well with me that my BSD header now relied on GPL headers, so my thinking is that many implementations in TypeUtils.h (I have already secured its re-licensing) and BitUtils.h can either be directly traced back to public domain sources, or can be best described as "the best and/or only way to perform this task." The precedent for public-domain-equivalent licensed files in the Dolphin Emulator project can be seen in Align.h, BitSet.h, TraversalClient.h/cpp, TraversalProto.h, TraversalServer.cpp, and LaggedFibonacciGenerator.h.h/cpp.

While I am not fond of the idea, there is also the option of taking my re-implemented bit extraction/insertion functions and putting them in a new header where I can freely license them as I choose. I have chosen the diplomatic approach because I think it is the better option.

Minty-Meeo avatar Oct 07 '22 03:10 Minty-Meeo

Here is a task list to keep track of progress getting the file re-licensed.

  • [x] Common::BitSize
  • [x] Common::ExtractBit variable & constant
  • [X] Common::ExtractBits variable & constant
    • New implementation
  • [x] Common::RotateLeft (see: #10950)
  • [x] Common::RotateRight (see: #10950)
  • [ ] Common::IsValidLowMask (counterpart to https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2)
  • [ ] Common::BitCast (see: #10957)
  • [ ] Common::BitCastPtrType
  • [ ] Common::BitCastPtr
  • [ ] Common::BitCastToArray
  • [ ] Common::BitCastFromArray void & returning
  • [X] Common::SetBit variable & constant
    • New implementation
  • [ ] Common::FlagBit
  • [ ] Common::Flags
  • [ ] Common::ExpandValue
  • [x] Common::CountLeadingZerosConst (see: #11130)
  • [x] Common::CountLeadingZeros 64-bit and 32-bit (see: #11130)
  • [x] Common::CountTrailingZerosConst (see: #11130)
  • [x] Common::CountTrailingZeros 64-bit and 32-bit (see: #11130)

Minty-Meeo avatar Oct 07 '22 03:10 Minty-Meeo

Just my take of course but I think if you're trying to make this more available for others to use (hence the more appropriate license), you should consider moving all this code out of Dolphin and into its own repo where it can then be pulled in as an external. Having it in the depths of Dolphin code base where it isn't that visible isn't really going to help anyone except the very curious.

iwubcode avatar Oct 07 '22 03:10 iwubcode

Got a bit bored and tacked some new stuff onto this PR. I found that there were lots of places where Extraction/Insertion of bits could replace existing code, but I also found a lot of places where unconditionally setting or clearing a bit would be useful (even if it is a short idiom). Thus, SetBit/ClearBit were born. They are only distantly related to the old SetBit function which was replaced by InsertBit. The only lineage you can really trace is the public domain idioms, anyhow.

Minty-Meeo avatar Oct 26 '22 07:10 Minty-Meeo 

* [ ]  Common::IsValidLowMask (counterpart to https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2)

As far as I'm concerned, I don't mind and approve re-licensing and/or modifying my contribution of IsValidLowMask in BitUtils.h and BitUtilsTest.cpp as necessary.

If you need more from me, just hit me up on Twitter @blubberdi or Discord Niels#6762

blubberdiblub avatar Nov 07 '22 16:11 blubberdiblub

Oh, thank you for replying. Unfortunately, this series of pull requests are on hiatus until Dolphin Emulator fully commits to C++20, which I speculate is whenever the Android NDK fully commits to C++20. It might be a while until then.

Minty-Meeo avatar Dec 13 '22 04:12 Minty-Meeo