Skip to content

Commit

Permalink
[crc64] Fix a subtle bug in CRC64 splice-by-8 implementation (#627)
Browse files Browse the repository at this point in the history 
Commit 9b88ce7 implemented a splice-by-8 version of the CRC64
algorithm which processes 8 bytes per loop iteration. However, the
code had a subtle bug which resulted in the same CRC calculated for
different strings and made some of the Xamarin.Android tests to fail.

The following strings yielded the same checksum value:

  * `obj/Debug/lp/10/jl/bin/classes.jar`
  * `obj/Debug/lp/11/jl/bin/classes.jar`
  * `obj/Debug/lp/12/jl/bin/classes.jar`

The reason for this was subtle (a stupid oversight on my part, really):
the loop fetched values from the input array by using an index into
the array:

	crc ^= (ulong)aptr[idx];

However, with `aptr` being declared as `byte* aptr` the indexing
operation returned a single *byte* instead of the required 64-bit word
(8 bytes) and, thus, on each iteration of the loop 7 bytes of the input
arrays were ignored in calculation, thus causing the collisions.

The fix is to cast `aptr` to `ulong*` and *then* index it, extracting
the required 8 bytes.

This commit also adds a test to check for this issue.
  • Loading branch information
@grendello @jonpryor
grendello authored and jonpryor committed Apr 22, 2020
1 parent 05c0d7d commit 933876c
Show file tree
Hide file tree
Showing 5 changed files with 60 additions and 22 deletions.
2 changes: 1 addition & 1 deletion src/Java.Interop.Tools.JavaCallableWrappers/Java.Interop.Tools.JavaCallableWrappers/Crc64.cs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -61,7 +61,7 @@ unsafe protected override void HashCore (byte [] array, int ibStart, int cbSize)
fixed (ulong* tptr = Table) {
fixed (byte* aptr = array) {
while (len >= 8) {
crc ^= (ulong)aptr[idx];
crc ^= *((ulong*)(aptr + idx));
crc =
tptr [7 * 256 + (crc & 0xff)] ^
tptr [6 * 256 + ((crc >> 8) & 0xff)] ^
Expand Down
40 changes: 39 additions & 1 deletion ...op.Tools.JavaCallableWrappers-Tests/Java.Interop.Tools.JavaCallableWrappers/Crc64Tests.cs
View file
Original file line number Diff line number Diff line change
@@ -1,4 +1,5 @@
using System.Text;
using System.Security.Cryptography;
using Java.Interop.Tools.JavaCallableWrappers;
using NUnit.Framework;

Expand Down Expand Up @@ -34,13 +35,50 @@ public void Hello ()
public void XmlDocument ()
{
var actual = ToHash ("System.Xml.XmlDocument, System.Xml");
Assert.AreEqual ("b9c1bdfc7cd47543", actual);
Assert.AreEqual ("348bbd9fecf1b865", actual);
}

[Test]
public void Collision ()
{
Assert.AreNotEqual (ToHash (""), ToHash (new byte [32]));
}

[Test]
public void AllBytesAreProcessed ()
{
// Slicing processes 8 bytes (a 64-bit word) at a time, and if any of the bytes are skipped we will have a
// collision here.
string[] inputs = {
"obj/Debug/lp/10/jl/bin/classes.jar",
"obj/Debug/lp/11/jl/bin/classes.jar",
"obj/Debug/lp/12/jl/bin/classes.jar",
};

string[] expected = {
"419a37c9bcfddf3c",
"6ea5e242b7cc24a7",
"74770a86f8b97020",
};

string[] outputs = new string[inputs.Length];

for (int i = 0; i < inputs.Length; i++) {
byte[] bytes = Encoding.UTF8.GetBytes (inputs [i]);
using (HashAlgorithm hashAlg = new Crc64 ()) {
byte [] hash = hashAlg.ComputeHash (bytes);
outputs[i] = ToHash (hash);
Assert.AreEqual (expected[i], outputs[i], $"hash {i} differs");
}
}

for (int i = 0; i < outputs.Length; i++) {
for (int j = 0; j < outputs.Length; j++) {
if (j == i)
continue;
Assert.AreNotEqual (outputs[i], outputs[j], $"Outputs {i} and {j} are identical");
}
}
}
}
}
14 changes: 7 additions & 7 deletions ...appers-Tests/Java.Interop.Tools.JavaCallableWrappers/JavaCallableWrapperGeneratorTests.cs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -124,7 +124,7 @@ public void GenerateIndirectApplication (
)
{
var actual = Generate (typeof (IndirectApplication), applicationJavaClass);
var expected = @"package c64r2b57424eba1fa9d27;
var expected = @"package c64r2197ae30a36756915;
public class IndirectApplication
Expand Down Expand Up @@ -175,7 +175,7 @@ public void monodroidClearReferences ()
public void GenerateExportedMembers ()
{
var actual = Generate (typeof (ExportsMembers));
var expected = @"package c64r2b57424eba1fa9d27;
var expected = @"package c64r2197ae30a36756915;
public class ExportsMembers
Expand All @@ -187,7 +187,7 @@ extends java.lang.Object
public static final String __md_methods;
static {
__md_methods =
""n_GetInstance:()Lc64r2b57424eba1fa9d27/ExportsMembers;:__export__\n"" +
""n_GetInstance:()Lc64r2197ae30a36756915/ExportsMembers;:__export__\n"" +
""n_GetValue:()Ljava/lang/String;:__export__\n"" +
""n_methodNamesNotMangled:()V:__export__\n"" +
""n_CompletelyDifferentName:(Ljava/lang/String;I)Ljava/lang/String;:__export__\n"" +
Expand All @@ -198,17 +198,17 @@ extends java.lang.Object
}
public static c64r2b57424eba1fa9d27.ExportsMembers STATIC_INSTANCE = GetInstance ();
public static c64r2197ae30a36756915.ExportsMembers STATIC_INSTANCE = GetInstance ();
public java.lang.String VALUE = GetValue ();
public static c64r2b57424eba1fa9d27.ExportsMembers GetInstance ()
public static c64r2197ae30a36756915.ExportsMembers GetInstance ()
{
return n_GetInstance ();
}
private static native c64r2b57424eba1fa9d27.ExportsMembers n_GetInstance ();
private static native c64r2197ae30a36756915.ExportsMembers n_GetInstance ();
public java.lang.String GetValue ()
{
Expand Down Expand Up @@ -271,7 +271,7 @@ public void monodroidClearReferences ()
public void GenerateInnerClass ()
{
var actual = Generate (typeof (ExampleOuterClass));
var expected = @"package c64r2b57424eba1fa9d27;
var expected = @"package c64r2197ae30a36756915;
public class ExampleOuterClass
Expand Down
2 changes: 1 addition & 1 deletion ...lableWrappers-Tests/Java.Interop.Tools.JavaCallableWrappers/JavaNativeTypeManagerTests.cs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -29,7 +29,7 @@ public void TearDown ()
public void Crc64 ()
{
JavaNativeTypeManager.PackageNamingPolicy = PackageNamingPolicy.LowercaseCrc64;
Assert.AreEqual ("c64r279bf423bcb581100", JavaNativeTypeManager.GetPackageName (typeof (string)));
Assert.AreEqual ("c64r2b74743e9328eed0a", JavaNativeTypeManager.GetPackageName (typeof (string)));
}

[Test]
Expand Down
24 changes: 12 additions & 12 deletions ...llableWrappers-Tests/Java.Interop.Tools.JavaCallableWrappers/TypeNameMapGeneratorTests.cs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -59,12 +59,12 @@ public void WriteJavaToManaged ()
"value-offset=" + offset + "\u0000" +
GetJ2MEntryLine (typeof (ActivityName), "activity/Name", offset, length) +
GetJ2MEntryLine (typeof (ApplicationName), "application/Name", offset, length) +
GetJ2MEntryLine (typeof (DefaultName), "c64r2b57424eba1fa9d27/DefaultName", offset, length) +
GetJ2MEntryLine (typeof (DefaultName.A), "c64r2b57424eba1fa9d27/DefaultName_A", offset, length) +
GetJ2MEntryLine (typeof (DefaultName.A.B), "c64r2b57424eba1fa9d27/DefaultName_A_B", offset, length) +
GetJ2MEntryLine (typeof (DefaultName.C.D), "c64r2b57424eba1fa9d27/DefaultName_C_D", offset, length) +
GetJ2MEntryLine (typeof (ExampleOuterClass), "c64r2b57424eba1fa9d27/ExampleOuterClass", offset, length) +
GetJ2MEntryLine (typeof (ExampleOuterClass.ExampleInnerClass), "c64r2b57424eba1fa9d27/ExampleOuterClass$ExampleOuterClass_ExampleInnerClass", offset, length) +
GetJ2MEntryLine (typeof (DefaultName), "c64r2197ae30a36756915/DefaultName", offset, length) +
GetJ2MEntryLine (typeof (DefaultName.A), "c64r2197ae30a36756915/DefaultName_A", offset, length) +
GetJ2MEntryLine (typeof (DefaultName.A.B), "c64r2197ae30a36756915/DefaultName_A_B", offset, length) +
GetJ2MEntryLine (typeof (DefaultName.C.D), "c64r2197ae30a36756915/DefaultName_C_D", offset, length) +
GetJ2MEntryLine (typeof (ExampleOuterClass), "c64r2197ae30a36756915/ExampleOuterClass", offset, length) +
GetJ2MEntryLine (typeof (ExampleOuterClass.ExampleInnerClass), "c64r2197ae30a36756915/ExampleOuterClass$ExampleOuterClass_ExampleInnerClass", offset, length) +
GetJ2MEntryLine (typeof (InstrumentationName), "instrumentation/Name", offset, length) +
GetJ2MEntryLine (typeof (AbstractClass), "my/AbstractClass", offset, length) +
GetJ2MEntryLine (typeof (ExampleActivity), "my/ExampleActivity", offset, length) +
Expand Down Expand Up @@ -139,14 +139,14 @@ public void WriteManagedToJava ()
GetM2JEntryLine (typeof (AbstractClassInvoker), "my/AbstractClass", offset, length) +
GetM2JEntryLine (typeof (ActivityName), "activity/Name", offset, length) +
GetM2JEntryLine (typeof (ApplicationName), "application/Name", offset, length) +
GetM2JEntryLine (typeof (DefaultName.A.B), "c64r2b57424eba1fa9d27/DefaultName_A_B", offset, length) +
GetM2JEntryLine (typeof (DefaultName.A), "c64r2b57424eba1fa9d27/DefaultName_A", offset, length) +
GetM2JEntryLine (typeof (DefaultName.C.D), "c64r2b57424eba1fa9d27/DefaultName_C_D", offset, length) +
GetM2JEntryLine (typeof (DefaultName), "c64r2b57424eba1fa9d27/DefaultName", offset, length) +
GetM2JEntryLine (typeof (DefaultName.A.B), "c64r2197ae30a36756915/DefaultName_A_B", offset, length) +
GetM2JEntryLine (typeof (DefaultName.A), "c64r2197ae30a36756915/DefaultName_A", offset, length) +
GetM2JEntryLine (typeof (DefaultName.C.D), "c64r2197ae30a36756915/DefaultName_C_D", offset, length) +
GetM2JEntryLine (typeof (DefaultName), "c64r2197ae30a36756915/DefaultName", offset, length) +
GetM2JEntryLine (typeof (ExampleActivity), "my/ExampleActivity", offset, length) +
GetM2JEntryLine (typeof (ExampleInstrumentation), "my/ExampleInstrumentation", offset, length) +
GetM2JEntryLine (typeof (ExampleOuterClass.ExampleInnerClass), "c64r2b57424eba1fa9d27/ExampleOuterClass$ExampleOuterClass_ExampleInnerClass", offset, length) +
GetM2JEntryLine (typeof (ExampleOuterClass), "c64r2b57424eba1fa9d27/ExampleOuterClass", offset, length) +
GetM2JEntryLine (typeof (ExampleOuterClass.ExampleInnerClass), "c64r2197ae30a36756915/ExampleOuterClass$ExampleOuterClass_ExampleInnerClass", offset, length) +
GetM2JEntryLine (typeof (ExampleOuterClass), "c64r2197ae30a36756915/ExampleOuterClass", offset, length) +
GetM2JEntryLine (typeof (InstrumentationName), "instrumentation/Name", offset, length) +
GetM2JEntryLine (typeof (NonStaticOuterClass.NonStaticInnerClass), "register/NonStaticOuterClass$NonStaticInnerClass", offset, length) +
GetM2JEntryLine (typeof (NonStaticOuterClass), "register/NonStaticOuterClass", offset, length) +
Expand Down

0 comments on commit 933876c

Please sign in to comment.