diff --git a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
index 32342fc..c1e8515 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
@@ -20,6 +20,7 @@
 import com.android.tools.r8.naming.signature.GenericSignatureParser;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
+import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.InternalOptions.PackageObfuscationMode;
 import com.android.tools.r8.utils.StringUtils;
@@ -39,15 +40,16 @@
   private final AppInfoWithLiveness appInfo;
   private final RootSet rootSet;
   private final PackageObfuscationMode packageObfuscationMode;
+  private final Set<String> usedPackagePrefixes = Sets.newHashSet();
   private final Set<DexString> usedTypeNames = Sets.newIdentityHashSet();
 
   private final Map<DexType, DexString> renaming = Maps.newIdentityHashMap();
-  private final Map<String, ClassNamingState> states = new HashMap<>();
+  private final Map<String, Namespace> states = new HashMap<>();
   private final ImmutableList<String> packageDictionary;
   private final ImmutableList<String> classDictionary;
   private final boolean keepInnerClassStructure;
 
-  private final ClassNamingState topLevelState;
+  private final Namespace topLevelState;
 
   private GenericSignatureRewriter genericSignatureRewriter = new GenericSignatureRewriter();
 
@@ -66,8 +68,8 @@
     this.keepInnerClassStructure = options.attributeRemoval.signature;
 
     // Initialize top-level naming state.
-    topLevelState = new ClassNamingState(getPackageBinaryNameFromJavaType(
-        options.proguardConfiguration.getPackagePrefix()));
+    topLevelState = new Namespace(
+        getPackageBinaryNameFromJavaType(options.proguardConfiguration.getPackagePrefix()));
     states.computeIfAbsent("", k -> topLevelState);
   }
 
@@ -144,6 +146,8 @@
    */
   private void registerClassAsUsed(DexType type) {
     renaming.put(type, type.descriptor);
+    registerPackagePrefixesAsUsed(
+        getParentPackagePrefix(getClassBinaryNameFromDescriptor(type.descriptor.toSourceString())));
     usedTypeNames.add(type.descriptor);
     if (keepInnerClassStructure) {
       DexType outerClass = getOutClassForType(type);
@@ -156,6 +160,17 @@
     }
   }
 
+  /**
+   * Registers the given package prefix and all of parent packages as used.
+   */
+  private void registerPackagePrefixesAsUsed(String packagePrefix) {
+    String usedPrefix = packagePrefix;
+    while (usedPrefix.length() > 0) {
+      usedPackagePrefixes.add(usedPrefix);
+      usedPrefix = getParentPackagePrefix(usedPrefix);
+    }
+  }
+
   private DexType getOutClassForType(DexType type) {
     DexClass clazz = appInfo.definitionFor(type);
     if (clazz == null) {
@@ -176,7 +191,7 @@
   }
 
   private DexString computeName(DexClass clazz) {
-    ClassNamingState state = null;
+    Namespace state = null;
     if (keepInnerClassStructure) {
       // When keeping the nesting structure of inner classes, we have to insert the name
       // of the outer class for the $ prefix.
@@ -186,22 +201,22 @@
       }
     }
     if (state == null) {
-      state = getStateFor(clazz);
+      state = getStateForClass(clazz);
     }
     return state.nextTypeName();
   }
 
-  private ClassNamingState getStateFor(DexClass clazz) {
+  private Namespace getStateForClass(DexClass clazz) {
     String packageName = getPackageBinaryNameFromJavaType(clazz.type.getPackageDescriptor());
     // Check whether the given class should be kept.
     if (rootSet.keepPackageName.contains(clazz)) {
-      return states.computeIfAbsent(packageName, ClassNamingState::new);
+      return states.computeIfAbsent(packageName, Namespace::new);
     }
-    ClassNamingState state = topLevelState;
+    Namespace state = topLevelState;
     switch (packageObfuscationMode) {
       case NONE:
-        // TODO(b/36799686): general obfuscation.
-        state = states.computeIfAbsent(packageName, ClassNamingState::new);
+        // For general obfuscation, rename all the involved package prefixes.
+        state = getStateForPackagePrefix(packageName);
         break;
       case REPACKAGE:
         // For repackaging, all classes are repackaged to a single package.
@@ -210,16 +225,29 @@
       case FLATTEN:
         // For flattening, all packages are repackaged to a single package.
         state = states.computeIfAbsent(packageName, k -> {
-          String renamedPackageName =
-              getClassBinaryNameFromDescriptor(topLevelState.nextSuggestedName());
-          return new ClassNamingState(renamedPackageName);
+          String renamedPackagePrefix = topLevelState.nextPackagePrefix();
+          return new Namespace(renamedPackagePrefix);
         });
         break;
     }
     return state;
   }
 
-  private ClassNamingState getStateForOuterClass(DexType outer) {
+  private Namespace getStateForPackagePrefix(String prefix) {
+    return states.computeIfAbsent(prefix, k -> {
+      // Calculate the parent package prefix, e.g., La/b/c -> La/b
+      String parentPackage = getParentPackagePrefix(prefix);
+      // Create a state for parent package prefix, if necessary, in a recursive manner.
+      // That recursion should end when the parent package hits the top-level, "".
+      Namespace superState = getStateForPackagePrefix(parentPackage);
+      // From the super state, get a renamed package prefix for the current level.
+      String renamedPackagePrefix = superState.nextPackagePrefix();
+      // Create a new state, which corresponds to a new name space, for the current level.
+      return new Namespace(renamedPackagePrefix);
+    });
+  }
+
+  private Namespace getStateForOuterClass(DexType outer) {
     String prefix = getClassBinaryNameFromDescriptor(outer.toDescriptorString());
     return states.computeIfAbsent(prefix, k -> {
       // Create a naming state with this classes renaming as prefix.
@@ -235,7 +263,7 @@
         }
       }
       String binaryName = getClassBinaryNameFromDescriptor(renamed.toString());
-      return new ClassNamingState(binaryName, "$");
+      return new Namespace(binaryName, "$");
     });
   }
 
@@ -256,46 +284,67 @@
     }
   }
 
-  private class ClassNamingState {
+  private class Namespace {
 
     private final char[] packagePrefix;
     private int typeCounter = 1;
-    private Iterator<String> dictionaryIterator;
+    private int packageCounter = 1;
+    private Iterator<String> packageDictionaryIterator;
+    private Iterator<String> classDictionaryIterator;
 
-    ClassNamingState(String packageName) {
+    Namespace(String packageName) {
       this(packageName, "/");
     }
 
-    ClassNamingState(String packageName, String separator) {
+    Namespace(String packageName, String separator) {
       this.packagePrefix = ("L" + packageName
           // L or La/b/ (or La/b/C$)
           + (packageName.isEmpty() ? "" : separator))
           .toCharArray();
-      // TODO(b/36799686): general obfuscation should use packageDictionary when renaming package.
-      this.dictionaryIterator = classDictionary.iterator();
+      this.packageDictionaryIterator = packageDictionary.iterator();
+      this.classDictionaryIterator = classDictionary.iterator();
     }
 
-    public char[] getPackagePrefix() {
-      return packagePrefix;
-    }
-
-    String nextSuggestedName() {
+    private String nextSuggestedNameForClass() {
       StringBuilder nextName = new StringBuilder();
-      if (dictionaryIterator.hasNext()) {
-        nextName.append(packagePrefix).append(dictionaryIterator.next()).append(';');
+      if (classDictionaryIterator.hasNext()) {
+        nextName.append(packagePrefix).append(classDictionaryIterator.next()).append(';');
         return nextName.toString();
       } else {
         return StringUtils.numberToIdentifier(packagePrefix, typeCounter++, true);
       }
     }
 
-    private DexString nextTypeName() {
+    DexString nextTypeName() {
       DexString candidate;
       do {
-        candidate = appInfo.dexItemFactory.createString(nextSuggestedName());
+        candidate = appInfo.dexItemFactory.createString(nextSuggestedNameForClass());
       } while (usedTypeNames.contains(candidate));
       return candidate;
     }
+
+    private String nextSuggestedNameForSubpackage() {
+      StringBuilder nextName = new StringBuilder();
+      // Note that the differences between this method and the other variant for class renaming are
+      // 1) this one uses the different dictionary and counter,
+      // 2) this one does not append ';' at the end, and
+      // 3) this one removes 'L' at the beginning to make the return value a binary form.
+      if (packageDictionaryIterator.hasNext()) {
+        nextName.append(packagePrefix).append(packageDictionaryIterator.next());
+      } else {
+        nextName.append(StringUtils.numberToIdentifier(packagePrefix, packageCounter++, false));
+      }
+      return nextName.toString().substring(1);
+    }
+
+    String nextPackagePrefix() {
+      String candidate;
+      do {
+        candidate = nextSuggestedNameForSubpackage();
+      } while (usedPackagePrefixes.contains(candidate));
+      return candidate;
+    }
+
   }
 
   private class GenericSignatureRewriter implements GenericSignatureAction<DexType> {
@@ -355,4 +404,18 @@
       // nothing to do
     }
   }
+
+  /**
+   * Compute parent package prefix from the given package prefix.
+   *
+   * @param packagePrefix i.e. "Ljava/lang"
+   * @return parent package prefix i.e. "Ljava"
+   */
+  static String getParentPackagePrefix(String packagePrefix) {
+    int i = packagePrefix.lastIndexOf(DescriptorUtils.DESCRIPTOR_PACKAGE_SEPARATOR);
+    if (i < 0) {
+      return "";
+    }
+    return packagePrefix.substring(0, i);
+  }
 }
diff --git a/src/test/examples/naming044/keep-rules-005.txt b/src/test/examples/naming044/keep-rules-005.txt
new file mode 100644
index 0000000..5583ccf
--- /dev/null
+++ b/src/test/examples/naming044/keep-rules-005.txt
@@ -0,0 +1,9 @@
+# Copyright (c) 2017, 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.
+
+-allowaccessmodification
+
+-keep,allowobfuscation class * {
+  *;
+}
diff --git a/src/test/examples/naming101/a/a.java b/src/test/examples/naming101/a/a.java
new file mode 100644
index 0000000..261bfc3
--- /dev/null
+++ b/src/test/examples/naming101/a/a.java
@@ -0,0 +1,8 @@
+// Copyright (c) 2017, 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 naming101.a;
+
+public class a {
+  static int f = 6;
+}
diff --git a/src/test/examples/naming101/a/b/c.java b/src/test/examples/naming101/a/b/c.java
new file mode 100644
index 0000000..b399bda
--- /dev/null
+++ b/src/test/examples/naming101/a/b/c.java
@@ -0,0 +1,8 @@
+// Copyright (c) 2017, 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 naming101.a.b;
+
+public class c {
+  static boolean flag = true;
+}
diff --git a/src/test/examples/naming101/a/c.java b/src/test/examples/naming101/a/c.java
new file mode 100644
index 0000000..fbf890b
--- /dev/null
+++ b/src/test/examples/naming101/a/c.java
@@ -0,0 +1,10 @@
+// Copyright (c) 2017, 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 naming101.a;
+
+public class c {
+  public static int a() {
+    return a.f;
+  }
+}
diff --git a/src/test/examples/naming101/b/a.java b/src/test/examples/naming101/b/a.java
new file mode 100644
index 0000000..c7eaa83
--- /dev/null
+++ b/src/test/examples/naming101/b/a.java
@@ -0,0 +1,8 @@
+// Copyright (c) 2017, 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 naming101.b;
+
+public class a {
+  static boolean flag = false;
+}
diff --git a/src/test/examples/naming101/b/b.java b/src/test/examples/naming101/b/b.java
new file mode 100644
index 0000000..db21bd3
--- /dev/null
+++ b/src/test/examples/naming101/b/b.java
@@ -0,0 +1,10 @@
+// Copyright (c) 2017, 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 naming101.b;
+
+public class b {
+  static boolean a() {
+    return a.flag;
+  }
+}
diff --git a/src/test/examples/naming101/c.java b/src/test/examples/naming101/c.java
new file mode 100644
index 0000000..7477024
--- /dev/null
+++ b/src/test/examples/naming101/c.java
@@ -0,0 +1,8 @@
+// Copyright (c) 2017, 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 naming101;
+
+public class c {
+  static int i = 1;
+}
diff --git a/src/test/examples/naming101/d.java b/src/test/examples/naming101/d.java
new file mode 100644
index 0000000..3bb8131
--- /dev/null
+++ b/src/test/examples/naming101/d.java
@@ -0,0 +1,10 @@
+// Copyright (c) 2017, 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 naming101;
+
+public class d {
+  static int c() {
+    return c.i;
+  }
+}
diff --git a/src/test/examples/naming101/keep-rules-001.txt b/src/test/examples/naming101/keep-rules-001.txt
new file mode 100644
index 0000000..a191b54
--- /dev/null
+++ b/src/test/examples/naming101/keep-rules-001.txt
@@ -0,0 +1,11 @@
+# Copyright (c) 2017, 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.
+
+-allowaccessmodification
+
+-repackageclasses ''
+
+-keep,allowobfuscation class * {
+  *;
+}
diff --git a/src/test/examples/naming101/keep-rules-002.txt b/src/test/examples/naming101/keep-rules-002.txt
new file mode 100644
index 0000000..bbdde22
--- /dev/null
+++ b/src/test/examples/naming101/keep-rules-002.txt
@@ -0,0 +1,15 @@
+# Copyright (c) 2017, 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.
+
+-allowaccessmodification
+
+-repackageclasses 'naming101.a'
+
+-keep public class **.a {
+  *;
+}
+
+-keep,allowobfuscation class * {
+  *;
+}
diff --git a/src/test/examples/naming101/keep-rules-003.txt b/src/test/examples/naming101/keep-rules-003.txt
new file mode 100644
index 0000000..10b2856
--- /dev/null
+++ b/src/test/examples/naming101/keep-rules-003.txt
@@ -0,0 +1,11 @@
+# Copyright (c) 2017, 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.
+
+-allowaccessmodification
+
+-flattenpackagehierarchy ''
+
+-keep,allowobfuscation class * {
+  *;
+}
diff --git a/src/test/examples/naming101/keep-rules-004.txt b/src/test/examples/naming101/keep-rules-004.txt
new file mode 100644
index 0000000..a4f3634
--- /dev/null
+++ b/src/test/examples/naming101/keep-rules-004.txt
@@ -0,0 +1,15 @@
+# Copyright (c) 2017, 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.
+
+-allowaccessmodification
+
+-flattenpackagehierarchy 'naming101'
+
+-keep public class **.a {
+  *;
+}
+
+-keep,allowobfuscation class * {
+  *;
+}
diff --git a/src/test/examples/naming101/keep-rules-005.txt b/src/test/examples/naming101/keep-rules-005.txt
new file mode 100644
index 0000000..5583ccf
--- /dev/null
+++ b/src/test/examples/naming101/keep-rules-005.txt
@@ -0,0 +1,9 @@
+# Copyright (c) 2017, 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.
+
+-allowaccessmodification
+
+-keep,allowobfuscation class * {
+  *;
+}
diff --git a/src/test/examples/shaking1/print-mapping.ref b/src/test/examples/shaking1/print-mapping.ref
index 8382304..b75dbd3 100644
--- a/src/test/examples/shaking1/print-mapping.ref
+++ b/src/test/examples/shaking1/print-mapping.ref
@@ -1,4 +1,4 @@
 shaking1.Shaking -> shaking1.Shaking:
-shaking1.Used -> shaking1.a:
+shaking1.Used -> a.a:
     java.lang.String name -> a
     java.lang.String method() -> a
diff --git a/src/test/java/com/android/tools/r8/naming/PackageNamingTest.java b/src/test/java/com/android/tools/r8/naming/PackageNamingTest.java
index feaf0d9..b8e22d2 100644
--- a/src/test/java/com/android/tools/r8/naming/PackageNamingTest.java
+++ b/src/test/java/com/android/tools/r8/naming/PackageNamingTest.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.naming;
 
+import static com.android.tools.r8.naming.ClassNameMinifier.getParentPackagePrefix;
 import static com.android.tools.r8.utils.DescriptorUtils.getPackageNameFromDescriptor;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
@@ -15,6 +16,7 @@
 import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.Timing;
 import com.google.common.base.CharMatcher;
+import com.google.common.collect.ImmutableList;
 import java.nio.file.Paths;
 import java.util.Arrays;
 import java.util.Collection;
@@ -45,13 +47,19 @@
 
   @Parameters(name = "test: {0} keep: {1}")
   public static Collection<Object[]> data() {
-    List<String> tests = Arrays.asList("naming044");
+    List<String> tests = Arrays.asList("naming044", "naming101");
 
     Map<String, BiConsumer<DexItemFactory, NamingLens>> inspections = new HashMap<>();
     inspections.put("naming044:keep-rules-001.txt", PackageNamingTest::test044_rule001);
     inspections.put("naming044:keep-rules-002.txt", PackageNamingTest::test044_rule002);
     inspections.put("naming044:keep-rules-003.txt", PackageNamingTest::test044_rule003);
     inspections.put("naming044:keep-rules-004.txt", PackageNamingTest::test044_rule004);
+    inspections.put("naming044:keep-rules-005.txt", PackageNamingTest::test044_rule005);
+    inspections.put("naming101:keep-rules-001.txt", PackageNamingTest::test101_rule001);
+    inspections.put("naming101:keep-rules-002.txt", PackageNamingTest::test101_rule002);
+    inspections.put("naming101:keep-rules-003.txt", PackageNamingTest::test101_rule003);
+    inspections.put("naming101:keep-rules-004.txt", PackageNamingTest::test101_rule004);
+    inspections.put("naming101:keep-rules-005.txt", PackageNamingTest::test101_rule005);
 
     return createTests(tests, inspections);
   }
@@ -135,4 +143,111 @@
         getPackageNameFromDescriptor(naming.lookupDescriptor(sub).toSourceString()),
         getPackageNameFromDescriptor(naming.lookupDescriptor(b).toSourceString()));
   }
+
+  private static void test044_rule005(DexItemFactory dexItemFactory, NamingLens naming) {
+    // All packages are renamed somehow. Need to check package hierarchy is consistent.
+    DexType a = dexItemFactory.createType("Lnaming044/A;");
+    assertEquals(1, countPackageDepth(naming.lookupDescriptor(a).toSourceString()));
+    DexType b = dexItemFactory.createType("Lnaming044/B;");
+    assertEquals(1, countPackageDepth(naming.lookupDescriptor(b).toSourceString()));
+    assertEquals(
+        getPackageNameFromDescriptor(naming.lookupDescriptor(a).toSourceString()),
+        getPackageNameFromDescriptor(naming.lookupDescriptor(b).toSourceString()));
+
+    DexType sub_a = dexItemFactory.createType("Lnaming044/sub/SubA;");
+    assertEquals(2, countPackageDepth(naming.lookupDescriptor(sub_a).toSourceString()));
+    DexType sub_b = dexItemFactory.createType("Lnaming044/sub/SubB;");
+    assertEquals(2, countPackageDepth(naming.lookupDescriptor(sub_b).toSourceString()));
+    assertEquals(
+        getPackageNameFromDescriptor(naming.lookupDescriptor(sub_a).toSourceString()),
+        getPackageNameFromDescriptor(naming.lookupDescriptor(sub_b).toSourceString()));
+
+    // Lnaming044/B -> La/c --prefix--> La
+    // Lnaming044/sub/SubB -> La/b/b --prefix--> La/b --prefix--> La
+    assertEquals(
+        getParentPackagePrefix(naming.lookupDescriptor(b).toSourceString()),
+        getParentPackagePrefix(
+            getParentPackagePrefix(naming.lookupDescriptor(sub_b).toSourceString())));
+  }
+
+  private static void test101_rule001(DexItemFactory dexItemFactory, NamingLens naming) {
+    // All classes are moved to the top-level package, hence no package separator.
+    DexType c = dexItemFactory.createType("Lnaming101/c;");
+    assertFalse(naming.lookupDescriptor(c).toSourceString().contains("/"));
+
+    DexType abc = dexItemFactory.createType("Lnaming101/a/b/c;");
+    assertFalse(naming.lookupDescriptor(abc).toSourceString().contains("/"));
+    assertNotEquals(
+        naming.lookupDescriptor(abc).toSourceString(),
+        naming.lookupDescriptor(c).toSourceString());
+  }
+
+  private static void test101_rule002(DexItemFactory dexItemFactory, NamingLens naming) {
+    // Check naming101.a.a is kept due to **.a
+    DexType a = dexItemFactory.createType("Lnaming101/a/a;");
+    assertEquals("Lnaming101/a/a;", naming.lookupDescriptor(a).toSourceString());
+    // Repackaged to naming101.a, but naming101.a.a exists to make a name conflict.
+    // Thus, everything else should not be renamed to 'a',
+    // except for naming101.b.a, which is also kept due to **.a
+    List<String> klasses = ImmutableList.of(
+        "Lnaming101/c;",
+        "Lnaming101/d;",
+        "Lnaming101/a/c;",
+        "Lnaming101/a/b/c;",
+        "Lnaming101/b/b;");
+    for (String klass : klasses) {
+      DexType k = dexItemFactory.createType(klass);
+      String renamedName = naming.lookupDescriptor(k).toSourceString();
+      assertEquals("naming101.a", getPackageNameFromDescriptor(renamedName));
+      assertNotEquals("Lnaming101/a/a;", renamedName);
+    }
+  }
+
+  private static void test101_rule003(DexItemFactory dexItemFactory, NamingLens naming) {
+    // All packages are moved to the top-level package, hence only one package separator.
+    DexType aa = dexItemFactory.createType("Lnaming101/a/a;");
+    assertEquals(1, countPackageDepth(naming.lookupDescriptor(aa).toSourceString()));
+
+    DexType ba = dexItemFactory.createType("Lnaming101/b/a;");
+    assertEquals(1, countPackageDepth(naming.lookupDescriptor(ba).toSourceString()));
+
+    assertNotEquals(
+        getPackageNameFromDescriptor(naming.lookupDescriptor(aa).toSourceString()),
+        getPackageNameFromDescriptor(naming.lookupDescriptor(ba).toSourceString()));
+  }
+
+  private static void test101_rule004(DexItemFactory dexItemFactory, NamingLens naming) {
+    // Check naming101.a.a is kept due to **.a
+    DexType a = dexItemFactory.createType("Lnaming101/a/a;");
+    assertEquals("Lnaming101/a/a;", naming.lookupDescriptor(a).toSourceString());
+    // Flattened to naming101, hence all other classes will be in naming101.* package.
+    // Due to naming101.a.a, prefix naming101.a is already used. So, any other classes,
+    // except for naming101.a.c, should not have naming101.a as package.
+    List<String> klasses = ImmutableList.of(
+        "Lnaming101/c;",
+        "Lnaming101/d;",
+        "Lnaming101/a/b/c;",
+        "Lnaming101/b/a;",
+        "Lnaming101/b/b;");
+    for (String klass : klasses) {
+      DexType k = dexItemFactory.createType(klass);
+      String renamedName = naming.lookupDescriptor(k).toSourceString();
+      assertNotEquals("naming101.a", getPackageNameFromDescriptor(renamedName));
+    }
+  }
+
+  private static void test101_rule005(DexItemFactory dexItemFactory, NamingLens naming) {
+    // All packages are renamed somehow. Need to check package hierarchy is consistent.
+    DexType aa = dexItemFactory.createType("Lnaming101/a/a;");
+    assertEquals(2, countPackageDepth(naming.lookupDescriptor(aa).toSourceString()));
+    DexType abc = dexItemFactory.createType("Lnaming101/a/b/c;");
+    assertEquals(3, countPackageDepth(naming.lookupDescriptor(abc).toSourceString()));
+
+    // Lnaming101/a/a; -> La/a/a; --prefix--> La/a
+    // Lnaming101/a/b/c; -> La/a/a/a; --prefix--> La/a/a --prefix--> La/a
+    assertEquals(
+        getParentPackagePrefix(naming.lookupDescriptor(aa).toSourceString()),
+        getParentPackagePrefix(
+            getParentPackagePrefix(naming.lookupDescriptor(abc).toSourceString())));
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/utils/DescriptorUtilsTest.java b/src/test/java/com/android/tools/r8/utils/DescriptorUtilsTest.java
index 034a288..58180e3 100644
--- a/src/test/java/com/android/tools/r8/utils/DescriptorUtilsTest.java
+++ b/src/test/java/com/android/tools/r8/utils/DescriptorUtilsTest.java
@@ -44,6 +44,15 @@
   }
 
   @Test
+  public void fromDescriptor() throws IOException {
+    String obj = "Ljava/lang/Object;";
+    assertEquals("Object", DescriptorUtils.getSimpleClassNameFromDescriptor(obj));
+    assertEquals("java.lang.Object", DescriptorUtils.getClassNameFromDescriptor(obj));
+    assertEquals("java.lang", DescriptorUtils.getPackageNameFromDescriptor(obj));
+    assertEquals("java/lang/Object", DescriptorUtils.getClassBinaryNameFromDescriptor(obj));
+  }
+
+  @Test
   public void toJavaType() throws IOException {
     assertEquals("boolean", DescriptorUtils.descriptorToJavaType("Z"));
     assertEquals("byte", DescriptorUtils.descriptorToJavaType("B"));