Fix IntegerUtil#getDivisorNumbers

Use unsigned mod operation for initialization of anc

Also includes
- https://github.com/PaperMC/DataConverter/commit/5a0cefb45e246ef36901fb62448571edd82e7296
- https://github.com/PaperMC/Starlight/commit/acc8ed9634bbe27ec68e8842e420948bfa9707e7

3 files changed, 68 insertions, 17 deletions

diff --git a/patches/server/0009-MC-Utils.patch b/patches/server/0009-MC-Utils.patch
index f5174018a6..5a0111aeda 100644
--- a/patches/server/0009-MC-Utils.patch
+++ b/patches/server/0009-MC-Utils.patch
@@ -3111,10 +3111,10 @@ index 0000000000000000000000000000000000000000..413e4b6da027876dbbe8eb78f2568a44
 +}
 diff --git a/src/main/java/io/papermc/paper/util/IntegerUtil.java b/src/main/java/io/papermc/paper/util/IntegerUtil.java
 new file mode 100644
-index 0000000000000000000000000000000000000000..a1bc1d1d0c86217ef18883d281195bc6b27e52ac
+index 0000000000000000000000000000000000000000..16785bd5c0524f6bad0691ca7ecd4514608d2eab
 --- /dev/null
 +++ b/src/main/java/io/papermc/paper/util/IntegerUtil.java
-@@ -0,0 +1,226 @@
+@@ -0,0 +1,242 @@
 +package io.papermc.paper.util;
 +
 +public final class IntegerUtil {
@@ -3214,7 +3214,7 @@ index 0000000000000000000000000000000000000000..a1bc1d1d0c86217ef18883d281195bc6
 +    // copied from hacker's delight (signed division magic value)
 +    // http://www.hackersdelight.org/hdcodetxt/magic.c.txt
 +    public static long getDivisorNumbers(final int d) {
-+        final int ad = IntegerUtil.branchlessAbs(d);
++        final int ad = branchlessAbs(d);
 +
 +        if (ad < 2) {
 +            throw new IllegalArgumentException("|number| must be in [2, 2^31 -1], not: " + d);
@@ -3223,11 +3223,27 @@ index 0000000000000000000000000000000000000000..a1bc1d1d0c86217ef18883d281195bc6
 +        final int two31 = 0x80000000;
 +        final long mask = 0xFFFFFFFFL; // mask for enforcing unsigned behaviour
 +
++        /*
++         Signed usage:
++         int number;
++         long magic = getDivisorNumbers(div);
++         long mul = magic >>> 32;
++         int sign = number >> 31;
++         int result = (int)(((long)number * mul) >>> magic) - sign;
++         */
++        /*
++         Unsigned usage:
++         int number;
++         long magic = getDivisorNumbers(div);
++         long mul = magic >>> 32;
++         int result = (int)(((long)number * mul) >>> magic);
++         */
++
 +        int p = 31;
 +
 +        // all these variables are UNSIGNED!
 +        int t = two31 + (d >>> 31);
-+        int anc = t - 1 - t%ad;
++        int anc = t - 1 - (int)((t & mask)%ad);
 +        int q1 = (int)((two31 & mask)/(anc & mask));
 +        int r1 = two31 - q1*anc;
 +        int q2 = (int)((two31 & mask)/(ad & mask));
@@ -3255,7 +3271,7 @@ index 0000000000000000000000000000000000000000..a1bc1d1d0c86217ef18883d281195bc6
 +        if (d < 0) {
 +            magicNum = -magicNum;
 +        }
-+        int shift = p - 32;
++        int shift = p;
 +        return ((long)magicNum << 32) | shift;
 +    }
 +
@@ -6690,7 +6706,7 @@ index a0b5895abc88d297045e05f25bb09527991d43f0..6e0bd0eab0b06a4ac3042496bbb91292
          super(type, world);
          this.xpReward = 5;
 diff --git a/src/main/java/net/minecraft/world/item/ItemStack.java b/src/main/java/net/minecraft/world/item/ItemStack.java
-index 6375dfa336d232c7876e184690a1cb5c9bc2c495..2e948330c4951e3df7091fa870573f163d2af286 100644
+index a797c6dd17cf73feada7badccf47b4036f746405..6758e72177c0a407cf6c392b10263f095e4d06e8 100644
 --- a/src/main/java/net/minecraft/world/item/ItemStack.java
 +++ b/src/main/java/net/minecraft/world/item/ItemStack.java
 @@ -788,6 +788,25 @@ public final class ItemStack {
diff --git a/patches/server/0015-Rewrite-dataconverter-system.patch b/patches/server/0015-Rewrite-dataconverter-system.patch
index 9cfe9ef895..35f36b25bb 100644
--- a/patches/server/0015-Rewrite-dataconverter-system.patch
+++ b/patches/server/0015-Rewrite-dataconverter-system.patch
@@ -582,10 +582,10 @@ index 0000000000000000000000000000000000000000..9ab4cb833c65d086122fc835217ce470
 +}
 diff --git a/src/main/java/ca/spottedleaf/dataconverter/minecraft/MCVersions.java b/src/main/java/ca/spottedleaf/dataconverter/minecraft/MCVersions.java
 new file mode 100644
-index 0000000000000000000000000000000000000000..dc62351262dc6e53935795ff0c5d03e3020f5ee2
+index 0000000000000000000000000000000000000000..2737b29fc872c64cd273182034eb22797ef4f900
 --- /dev/null
 +++ b/src/main/java/ca/spottedleaf/dataconverter/minecraft/MCVersions.java
-@@ -0,0 +1,471 @@
+@@ -0,0 +1,474 @@
 +package ca.spottedleaf.dataconverter.minecraft;
 +
 +@SuppressWarnings("unused")
@@ -1055,6 +1055,9 @@ index 0000000000000000000000000000000000000000..dc62351262dc6e53935795ff0c5d03e3
 +    public static final int V1_20_PRE6            = 3460;
 +    public static final int V1_20_PRE7            = 3461;
 +    public static final int V1_20_RC1             = 3462;
++    public static final int V1_20                 = 3463;
++    public static final int V1_20_1_RC1           = 3464;
++    public static final int V1_20_1               = 3465;
 +
 +}
 diff --git a/src/main/java/ca/spottedleaf/dataconverter/minecraft/converters/advancements/ConverterAbstractAdvancementsRename.java b/src/main/java/ca/spottedleaf/dataconverter/minecraft/converters/advancements/ConverterAbstractAdvancementsRename.java
@@ -23273,10 +23276,10 @@ index 0000000000000000000000000000000000000000..de9d632489609136c712a9adaee941fd
 +}
 diff --git a/src/main/java/ca/spottedleaf/dataconverter/util/IntegerUtil.java b/src/main/java/ca/spottedleaf/dataconverter/util/IntegerUtil.java
 new file mode 100644
-index 0000000000000000000000000000000000000000..b5ebf6bbe1a3711111cf045ee8b46c934c7e4563
+index 0000000000000000000000000000000000000000..4bbf38c812feeb30d2aa5f3fcf482bfcbed79d05
 --- /dev/null
 +++ b/src/main/java/ca/spottedleaf/dataconverter/util/IntegerUtil.java
-@@ -0,0 +1,223 @@
+@@ -0,0 +1,239 @@
 +package ca.spottedleaf.dataconverter.util;
 +
 +public final class IntegerUtil {
@@ -23373,7 +23376,7 @@ index 0000000000000000000000000000000000000000..b5ebf6bbe1a3711111cf045ee8b46c93
 +    }
 +
 +    public static long getDivisorNumbers(final int d) {
-+        final int ad = Math.abs(d);
++        final int ad = branchlessAbs(d);
 +
 +        if (ad < 2) {
 +            throw new IllegalArgumentException("|number| must be in [2, 2^31 -1], not: " + d);
@@ -23382,6 +23385,22 @@ index 0000000000000000000000000000000000000000..b5ebf6bbe1a3711111cf045ee8b46c93
 +        final int two31 = 0x80000000;
 +        final long mask = 0xFFFFFFFFL; // mask for enforcing unsigned behaviour
 +
++        /*
++         Signed usage:
++         int number;
++         long magic = getDivisorNumbers(div);
++         long mul = magic >>> 32;
++         int sign = number >> 31;
++         int result = (int)(((long)number * mul) >>> magic) - sign;
++         */
++        /*
++         Unsigned usage:
++         int number;
++         long magic = getDivisorNumbers(div);
++         long mul = magic >>> 32;
++         int result = (int)(((long)number * mul) >>> magic);
++         */
++
 +        int p = 31;
 +
 +        // all these variables are UNSIGNED!
@@ -23414,7 +23433,7 @@ index 0000000000000000000000000000000000000000..b5ebf6bbe1a3711111cf045ee8b46c93
 +        if (d < 0) {
 +            magicNum = -magicNum;
 +        }
-+        int shift = p - 32;
++        int shift = p;
 +        return ((long)magicNum << 32) | shift;
 +    }
 +
diff --git a/patches/server/0016-Starlight.patch b/patches/server/0016-Starlight.patch
index 5f43306bab..2cedc9864f 100644
--- a/patches/server/0016-Starlight.patch
+++ b/patches/server/0016-Starlight.patch
@@ -3848,10 +3848,10 @@ index 0000000000000000000000000000000000000000..16a4a14e7ccf9e4d7fdf1166674fe8f5
 +}
 diff --git a/src/main/java/ca/spottedleaf/starlight/common/util/IntegerUtil.java b/src/main/java/ca/spottedleaf/starlight/common/util/IntegerUtil.java
 new file mode 100644
-index 0000000000000000000000000000000000000000..177d0a969f3d72a34e773e8309c3719a235ee06d
+index 0000000000000000000000000000000000000000..fabf1e97c019c7365212f40018dcd08d3b828113
 --- /dev/null
 +++ b/src/main/java/ca/spottedleaf/starlight/common/util/IntegerUtil.java
-@@ -0,0 +1,226 @@
+@@ -0,0 +1,242 @@
 +package ca.spottedleaf.starlight.common.util;
 +
 +public final class IntegerUtil {
@@ -3951,7 +3951,7 @@ index 0000000000000000000000000000000000000000..177d0a969f3d72a34e773e8309c3719a
 +    // copied from hacker's delight (signed division magic value)
 +    // http://www.hackersdelight.org/hdcodetxt/magic.c.txt
 +    public static long getDivisorNumbers(final int d) {
-+        final int ad = IntegerUtil.branchlessAbs(d);
++        final int ad = branchlessAbs(d);
 +
 +        if (ad < 2) {
 +            throw new IllegalArgumentException("|number| must be in [2, 2^31 -1], not: " + d);
@@ -3960,11 +3960,27 @@ index 0000000000000000000000000000000000000000..177d0a969f3d72a34e773e8309c3719a
 +        final int two31 = 0x80000000;
 +        final long mask = 0xFFFFFFFFL; // mask for enforcing unsigned behaviour
 +
++        /*
++         Signed usage:
++         int number;
++         long magic = getDivisorNumbers(div);
++         long mul = magic >>> 32;
++         int sign = number >> 31;
++         int result = (int)(((long)number * mul) >>> magic) - sign;
++         */
++        /*
++         Unsigned usage:
++         int number;
++         long magic = getDivisorNumbers(div);
++         long mul = magic >>> 32;
++         int result = (int)(((long)number * mul) >>> magic);
++         */
++
 +        int p = 31;
 +
 +        // all these variables are UNSIGNED!
 +        int t = two31 + (d >>> 31);
-+        int anc = t - 1 - t%ad;
++        int anc = t - 1 - (int)((t & mask)%ad);
 +        int q1 = (int)((two31 & mask)/(anc & mask));
 +        int r1 = two31 - q1*anc;
 +        int q2 = (int)((two31 & mask)/(ad & mask));
@@ -3992,7 +4008,7 @@ index 0000000000000000000000000000000000000000..177d0a969f3d72a34e773e8309c3719a
 +        if (d < 0) {
 +            magicNum = -magicNum;
 +        }
-+        int shift = p - 32;
++        int shift = p;
 +        return ((long)magicNum << 32) | shift;
 +    }
 +