diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 1315918..05e7e22 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "1.6.44";
+  public static final String LABEL = "1.6.45";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/dex/ClassesChecksum.java b/src/main/java/com/android/tools/r8/dex/ClassesChecksum.java
index 07d2176..eaff74e 100644
--- a/src/main/java/com/android/tools/r8/dex/ClassesChecksum.java
+++ b/src/main/java/com/android/tools/r8/dex/ClassesChecksum.java
@@ -7,11 +7,13 @@
 import com.google.gson.JsonSyntaxException;
 import it.unimi.dsi.fastutil.objects.Object2LongMap;
 import it.unimi.dsi.fastutil.objects.Object2LongOpenHashMap;
+import java.io.UTFDataFormatException;
 import java.util.Comparator;
 import java.util.Map;
 
 public class ClassesChecksum {
 
+  private static final String PREFIX = "~~~";
   private static final char PREFIX_CHAR0 = '~';
   private static final char PREFIX_CHAR1 = '~';
   private static final char PREFIX_CHAR2 = '~';
@@ -19,6 +21,10 @@
   private Object2LongMap<String> dictionary = null;
 
   public ClassesChecksum() {
+    assert PREFIX.length() == 3;
+    assert PREFIX.charAt(0) == PREFIX_CHAR0;
+    assert PREFIX.charAt(1) == PREFIX_CHAR1;
+    assert PREFIX.charAt(2) == PREFIX_CHAR2;
   }
 
   private void ensureMap() {
@@ -71,12 +77,29 @@
     }
   }
 
-  public static boolean preceedChecksumMarker(DexString string) {
-    return string.size < 1 ||
-        string.content[0] < PREFIX_CHAR0 ||
-        string.size < 2 ||
-        string.content[1] < PREFIX_CHAR1 ||
-        string.size < 3 ||
-        string.content[2] < PREFIX_CHAR2;
+  /**
+   * Check if this string will definitely preceded the checksum marker.
+   *
+   * <p>If true is returned the string passed definitely preceded the checksum marker. If false is
+   * returned the string passed might still preceded, so this can give false negatives.
+   *
+   * @param string String to check if definitely preceded the checksum marker.
+   * @return If the string passed definitely preceded the checksum marker
+   */
+  public static boolean definitelyPrecedesChecksumMarker(DexString string) {
+    try {
+      assert PREFIX.length() == 3;
+      char[] prefix = new char[PREFIX.length()];
+      int prefixLength = string.decodePrefix(prefix);
+      return prefixLength == 0
+          || (prefixLength == 1 && prefix[0] <= PREFIX_CHAR0)
+          || (prefixLength == 2 && prefix[0] == PREFIX_CHAR0 && prefix[1] <= PREFIX_CHAR1)
+          || (prefixLength == 3
+              && prefix[0] == PREFIX_CHAR0
+              && prefix[1] == PREFIX_CHAR1
+              && prefix[2] < PREFIX_CHAR2);
+    } catch (UTFDataFormatException e) {
+      throw new RuntimeException("Bad format", e);
+    }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/dex/DexParser.java b/src/main/java/com/android/tools/r8/dex/DexParser.java
index e722669..34244b7 100644
--- a/src/main/java/com/android/tools/r8/dex/DexParser.java
+++ b/src/main/java/com/android/tools/r8/dex/DexParser.java
@@ -715,7 +715,7 @@
       AnnotationsDirectory annotationsDirectory = annotationsDirectoryAt(annotationsOffsets[i]);
 
       Long checksum = null;
-      if (checksums != null && classDataOffsets[i] != 0) {
+      if (checksums != null) {
         String desc = type.descriptor.toASCIIString();
         checksum = checksums.getOrDefault(desc, null);
         if (!options.dexClassChecksumFilter.test(desc, checksum)) {
@@ -950,7 +950,7 @@
     ClassesChecksum parsedChecksums = new ClassesChecksum();
     for (int i = stringIDs.length - 1; i >= 0; i--) {
       DexString value = indexedItems.getString(i);
-      if (ClassesChecksum.preceedChecksumMarker(value)) {
+      if (ClassesChecksum.definitelyPrecedesChecksumMarker(value)) {
         break;
       }
       parsedChecksums.tryParseAndAppend(value);
diff --git a/src/main/java/com/android/tools/r8/graph/DexString.java b/src/main/java/com/android/tools/r8/graph/DexString.java
index bac6fe3..131cee6 100644
--- a/src/main/java/com/android/tools/r8/graph/DexString.java
+++ b/src/main/java/com/android/tools/r8/graph/DexString.java
@@ -111,32 +111,46 @@
     return result;
   }
 
-  // Inspired from /dex/src/main/java/com/android/dex/Mutf8.java
   private String decode() throws UTFDataFormatException {
+    char[] out = new char[size];
+    int decodedLength = decodePrefix(out);
+    return new String(out, 0, decodedLength);
+  }
+
+  // Inspired from /dex/src/main/java/com/android/dex/Mutf8.java
+  public int decodePrefix(char[] out) throws UTFDataFormatException {
     int s = 0;
     int p = 0;
-    char[] out = new char[size];
+    int prefixLength = out.length;
     while (true) {
       char a = (char) (content[p++] & 0xff);
       if (a == 0) {
-        return new String(out, 0, s);
+        return s;
       }
       out[s] = a;
       if (a < '\u0080') {
-        s++;
+        if (++s == prefixLength) {
+          return s;
+        }
       } else if ((a & 0xe0) == 0xc0) {
         int b = content[p++] & 0xff;
         if ((b & 0xC0) != 0x80) {
           throw new UTFDataFormatException("bad second byte");
         }
-        out[s++] = (char) (((a & 0x1F) << 6) | (b & 0x3F));
+        out[s] = (char) (((a & 0x1F) << 6) | (b & 0x3F));
+        if (++s == prefixLength) {
+          return s;
+        }
       } else if ((a & 0xf0) == 0xe0) {
         int b = content[p++] & 0xff;
         int c = content[p++] & 0xff;
         if (((b & 0xC0) != 0x80) || ((c & 0xC0) != 0x80)) {
           throw new UTFDataFormatException("bad second or third byte");
         }
-        out[s++] = (char) (((a & 0x0F) << 12) | ((b & 0x3F) << 6) | (c & 0x3F));
+        out[s] = (char) (((a & 0x0F) << 12) | ((b & 0x3F) << 6) | (c & 0x3F));
+        if (++s == prefixLength) {
+          return s;
+        }
       } else {
         throw new UTFDataFormatException("bad byte");
       }
diff --git a/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsClassWithNoMethodsTest.java b/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsClassWithNoMethodsTest.java
new file mode 100644
index 0000000..9161a5d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsClassWithNoMethodsTest.java
@@ -0,0 +1,79 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.dexfilemerger;
+
+import static org.objectweb.asm.Opcodes.V1_8;
+
+import com.android.tools.r8.CompilationMode;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import java.nio.file.Path;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.objectweb.asm.ClassWriter;
+import org.objectweb.asm.Opcodes;
+
+@RunWith(Parameterized.class)
+public class DexMergeChecksumsClassWithNoMethodsTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withDexRuntimes().withAllApiLevels().build();
+  }
+
+  public DexMergeChecksumsClassWithNoMethodsTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testChecksumForClassWithNoMethods() throws Exception {
+    ClassWriter cw = new ClassWriter(0);
+    cw.visit(
+        V1_8,
+        Opcodes.ACC_PUBLIC | Opcodes.ACC_SUPER,
+        this.getClass().getTypeName().replace('.', '/') + "$" + "A",
+        null,
+        "java/lang/Object",
+        null);
+    cw.visitEnd();
+
+    Path dexArchiveA =
+        testForD8()
+            .setMinApi(parameters.getApiLevel())
+            .addProgramClassFileData(cw.toByteArray())
+            .setMode(CompilationMode.DEBUG)
+            .setIncludeClassesChecksum(true)
+            .compile().writeToZip();
+
+    Path dexArchiveTestClass =
+        testForD8()
+            .setMinApi(parameters.getApiLevel())
+            .addProgramClasses(TestClass.class)
+            .setMode(CompilationMode.DEBUG)
+            .setIncludeClassesChecksum(true)
+            .compile()
+            .writeToZip();
+
+    testForD8()
+        .setMinApi(parameters.getApiLevel())
+        .addProgramFiles(dexArchiveA, dexArchiveTestClass)
+        .setIncludeClassesChecksum(true)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines(this.getClass().getSimpleName() + "$A");
+  }
+
+  class A {}
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      System.out.println(A.class.getSimpleName());
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsHighSortingStrings.java b/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsHighSortingStrings.java
new file mode 100644
index 0000000..c5ad260
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsHighSortingStrings.java
@@ -0,0 +1,128 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.dexfilemerger;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.CompilationMode;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.dex.ClassesChecksum;
+import com.android.tools.r8.graph.DexItemFactory;
+import java.nio.file.Path;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class DexMergeChecksumsHighSortingStrings extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withDexRuntimes().withAllApiLevels().build();
+  }
+
+  public DexMergeChecksumsHighSortingStrings(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testChecksumWhitHighSortingStrings() throws Exception {
+    Path dexArchive1 =
+        testForD8()
+            .addProgramClasses(TestClass1.class)
+            .setMinApi(parameters.getApiLevel())
+            .setMode(CompilationMode.DEBUG)
+            .setIncludeClassesChecksum(true)
+            .compile()
+            .writeToZip();
+
+    Path dexArchive2 =
+        testForD8()
+            .addProgramClasses(TestClass2.class)
+            .setMinApi(parameters.getApiLevel())
+            .setMode(CompilationMode.DEBUG)
+            .setIncludeClassesChecksum(true)
+            .compile()
+            .writeToZip();
+
+    testForD8()
+        .setMinApi(parameters.getApiLevel())
+        .addProgramFiles(dexArchive1)
+        .setIncludeClassesChecksum(true)
+        .run(parameters.getRuntime(), TestClass1.class)
+        .assertSuccessWithOutputLines("Hello, \uDB3F\uDFFD");
+
+    testForD8()
+        .setMinApi(parameters.getApiLevel())
+        .addProgramFiles(dexArchive2)
+        .setIncludeClassesChecksum(true)
+        .run(parameters.getRuntime(), TestClass2.class)
+        .assertSuccessWithOutputLines("Hello, ~~~\u007f");
+
+    testForD8()
+        .setMinApi(parameters.getApiLevel())
+        .addProgramFiles(dexArchive1, dexArchive2)
+        .setIncludeClassesChecksum(true)
+        .run(parameters.getRuntime(), TestClass2.class)
+        .assertSuccessWithOutputLines("Hello, ~~~\u007f");
+  }
+
+  static class TestClass1 {
+    // U+DFFFD which is very end of unassigned plane.
+    private static final String STRING_SORTING_ABOVE_CHECKSUM_STRING = "\uDB3F\uDFFD";
+
+    public static void main(String[] args) {
+      System.out.println("Hello, " + STRING_SORTING_ABOVE_CHECKSUM_STRING);
+    }
+  }
+
+  static class TestClass2 {
+    private static final String STRING_SORTING_ABOVE_CHECKSUM_STRING = "~~~\u007f";
+
+    public static void main(String[] args) {
+      System.out.println("Hello, " + STRING_SORTING_ABOVE_CHECKSUM_STRING);
+    }
+  }
+
+  @Test
+  public void testChecksumMarkerComparison() {
+    // z     {     |     }     ~     <DEL>
+    // 0x7a  0x7b  0x7c  0x7d  0x7e  0x7f
+    assertTrue('{' - 1 == 'z');
+    assertTrue('{' + 1 == '|');
+    assertTrue('~' - 1 == '}');
+
+    DexItemFactory factory = new DexItemFactory();
+    assertFalse(
+        ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("\uDB3F\uDFFD")));
+    assertFalse(
+        ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~\uDB3F\uDFFD\"")));
+    assertFalse(
+        ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~\uDB3F\uDFFD")));
+    assertFalse(
+        ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~~\uDB3F\uDFFD")));
+    assertFalse(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("\u007f")));
+    assertFalse(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~\u007f")));
+    assertFalse(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~\u007f")));
+    assertFalse(
+        ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~~\u007f")));
+    assertFalse(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~~|")));
+
+    assertTrue(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~}")));
+    assertTrue(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~")));
+    assertTrue(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~}")));
+    assertTrue(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~")));
+    assertTrue(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("}")));
+
+    // False negatives.
+    assertFalse(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~~")));
+    assertFalse(ClassesChecksum.definitelyPrecedesChecksumMarker(factory.createString("~~~z")));
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsMarkerInterfaceTest.java b/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsMarkerInterfaceTest.java
new file mode 100644
index 0000000..b64ca95
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/dexfilemerger/DexMergeChecksumsMarkerInterfaceTest.java
@@ -0,0 +1,66 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.dexfilemerger;
+
+import com.android.tools.r8.CompilationMode;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import java.nio.file.Path;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class DexMergeChecksumsMarkerInterfaceTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withDexRuntimes().withAllApiLevels().build();
+  }
+
+  public DexMergeChecksumsMarkerInterfaceTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testChecksumForMarkerInterface() throws Exception {
+    Path dexArchiveI =
+        testForD8()
+            .setMinApi(parameters.getApiLevel())
+            .addProgramClasses(I.class)
+            .setMode(CompilationMode.DEBUG)
+            .setIncludeClassesChecksum(true)
+            .compile()
+            .writeToZip();
+
+    Path dexArchiveTestClass =
+        testForD8()
+            .setMinApi(parameters.getApiLevel())
+            .addProgramClasses(TestClass.class)
+            .setMode(CompilationMode.DEBUG)
+            .setIncludeClassesChecksum(true)
+            .compile()
+            .writeToZip();
+
+    testForD8()
+        .setMinApi(parameters.getApiLevel())
+        .addProgramFiles(dexArchiveI, dexArchiveTestClass)
+        .setIncludeClassesChecksum(true)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("Hello, world!");
+  }
+
+  interface I {}
+
+  static class TestClass implements I {
+
+    public static void main(String[] args) {
+      System.out.println("Hello, world!");
+    }
+  }
+}