diff --git a/tools/sepolicy_generate_compat.py b/tools/sepolicy_generate_compat.py
index 317a00e..17a4d75 100644
--- a/tools/sepolicy_generate_compat.py
+++ b/tools/sepolicy_generate_compat.py
@@ -23,11 +23,23 @@
 import policy
 import shutil
 import subprocess
+import sys
 import tempfile
 import zipfile
 """This tool generates a mapping file for {ver} core sepolicy."""
 
 temp_dir = ''
+compat_cil_template = ";; This file can't be empty.\n"
+ignore_cil_template = """;; new_objects - a collection of types that have been introduced that have no
+;;   analogue in older policy.  Thus, we do not need to map these types to
+;;   previous ones.  Add here to pass checkapi tests.
+(type new_objects)
+(typeattribute new_objects)
+(typeattributeset new_objects
+  ( new_objects
+    %s
+  ))
+"""
 
 
 def check_run(cmd, cwd=None):
@@ -88,12 +100,12 @@
 
     cmd = [
         'debugfs', '-R',
-        'cat system/etc/selinux/mapping/%s.cil' % ver, img_path
+        'cat system/etc/selinux/mapping/10000.0.cil', img_path
     ]
     path = os.path.join(destination, '%s.cil' % ver)
     with open(path, 'wb') as f:
         logging.debug('Extracting %s.cil to %s' % (ver, destination))
-        f.write(check_output(cmd).stdout)
+        f.write(check_output(cmd).stdout.replace(b'10000.0',b'33.0').replace(b'10000_0',b'33_0'))
     return path
 
 
@@ -156,6 +168,28 @@
     return base_policy_path, old_policy_path, pub_policy_cil_path
 
 
+def change_api_level(versioned_type, api_from, api_to):
+    """ Verifies the API version of versioned_type, and changes it to new API level.
+
+    For example, change_api_level("foo_32_0", "32.0", "31.0") will return
+    "foo_31_0".
+
+    Args:
+      versioned_type: string, type with version suffix
+      api_from: string, api version of versioned_type
+      api_to: string, new api version for versioned_type
+
+    Returns:
+      string, a new versioned type
+    """
+    old_suffix = api_from.replace('.', '_')
+    new_suffix = api_to.replace('.', '_')
+    if not versioned_type.endswith(old_suffix):
+        raise ValueError('Version of type %s is different from %s' %
+                         (versioned_type, api_from))
+    return versioned_type.removesuffix(old_suffix) + new_suffix
+
+
 def get_args():
     parser = argparse.ArgumentParser()
     parser.add_argument(
@@ -202,12 +236,10 @@
 
         build_top = get_android_build_top()
         sepolicy_path = os.path.join(build_top, 'system', 'sepolicy')
-        target_compat_path = os.path.join(sepolicy_path, 'private', 'compat',
-                                          args.target_version)
 
         # Step 1. Download system/etc/selinux/mapping/{ver}.cil, and remove types/typeattributes
-        mapping_file = download_mapping_file(args.branch, args.build,
-                                             args.target_version)
+        mapping_file = download_mapping_file(
+            args.branch, args.build, args.target_version, destination=temp_dir)
         mapping_file_cil = mini_parser.MiniCilParser(mapping_file)
         mapping_file_cil.types = set()
         mapping_file_cil.typeattributes = set()
@@ -231,7 +263,110 @@
         logging.info('new types: %s' % new_types)
         logging.info('removed types: %s' % removed_types)
 
-        # TODO: Step 4. Map new types and removed types appropriately
+        # Step 4. Map new types and removed types appropriately, based on the latest mapping
+        latest_compat_path = os.path.join(sepolicy_path, 'private', 'compat',
+                                          args.latest_version)
+        latest_mapping_cil = mini_parser.MiniCilParser(
+            os.path.join(latest_compat_path, args.latest_version + '.cil'))
+        latest_ignore_cil = mini_parser.MiniCilParser(
+            os.path.join(latest_compat_path,
+                         args.latest_version + '.ignore.cil'))
+
+        latest_ignored_types = list(latest_ignore_cil.rTypeattributesets.keys())
+        latest_removed_types = latest_mapping_cil.types
+        logging.debug('types ignored in latest policy: %s' %
+                      latest_ignored_types)
+        logging.debug('types removed in latest policy: %s' %
+                      latest_removed_types)
+
+        target_ignored_types = set()
+        target_removed_types = set()
+        invalid_new_types = set()
+        invalid_mapping_types = set()
+        invalid_removed_types = set()
+
+        logging.info('starting mapping')
+        for new_type in new_types:
+            # Either each new type should be in latest_ignore_cil, or mapped to existing types
+            if new_type in latest_ignored_types:
+                logging.debug('adding %s to ignore' % new_type)
+                target_ignored_types.add(new_type)
+            elif new_type in latest_mapping_cil.rTypeattributesets:
+                latest_mapped_types = latest_mapping_cil.rTypeattributesets[
+                    new_type]
+                target_mapped_types = {change_api_level(t, args.latest_version,
+                                        args.target_version)
+                       for t in latest_mapped_types}
+                logging.debug('mapping %s to %s' %
+                              (new_type, target_mapped_types))
+
+                for t in target_mapped_types:
+                    if t not in mapping_file_cil.typeattributesets:
+                        logging.error(
+                            'Cannot find desired type %s in mapping file' % t)
+                        invalid_mapping_types.add(t)
+                        continue
+                    mapping_file_cil.typeattributesets[t].add(new_type)
+            else:
+                logging.error('no mapping information for new type %s' %
+                              new_type)
+                invalid_new_types.add(new_type)
+
+        for removed_type in removed_types:
+            # Removed type should be in latest_mapping_cil
+            if removed_type in latest_removed_types:
+                logging.debug('adding %s to removed' % removed_type)
+                target_removed_types.add(removed_type)
+            else:
+                logging.error('no mapping information for removed type %s' %
+                              removed_type)
+                invalid_removed_types.add(removed_type)
+
+        error_msg = ''
+
+        if invalid_new_types:
+            error_msg += ('The following new types were not in the latest '
+                          'mapping: %s\n') % sorted(invalid_new_types)
+        if invalid_mapping_types:
+            error_msg += (
+                'The following existing types were not in the '
+                'downloaded mapping file: %s\n') % sorted(invalid_mapping_types)
+        if invalid_removed_types:
+            error_msg += ('The following removed types were not in the latest '
+                          'mapping: %s\n') % sorted(invalid_removed_types)
+
+        if error_msg:
+            error_msg += '\n'
+            error_msg += ('Please make sure the source tree and the build ID is'
+                          ' up to date.\n')
+            sys.exit(error_msg)
+
+        # Step 5. Write to system/sepolicy/private/compat
+        target_compat_path = os.path.join(sepolicy_path, 'private', 'compat',
+                                          args.target_version)
+        target_mapping_file = os.path.join(target_compat_path,
+                                           args.target_version + '.cil')
+        target_compat_file = os.path.join(target_compat_path,
+                                          args.target_version + '.compat.cil')
+        target_ignore_file = os.path.join(target_compat_path,
+                                          args.target_version + '.ignore.cil')
+
+        with open(target_mapping_file, 'w') as f:
+            logging.info('writing %s' % target_mapping_file)
+            if removed_types:
+                f.write(';; types removed from current policy\n')
+                f.write('\n'.join(f'(type {x})' for x in sorted(target_removed_types)))
+                f.write('\n\n')
+            f.write(mapping_file_cil.unparse())
+
+        with open(target_compat_file, 'w') as f:
+            logging.info('writing %s' % target_compat_file)
+            f.write(compat_cil_template)
+
+        with open(target_ignore_file, 'w') as f:
+            logging.info('writing %s' % target_ignore_file)
+            f.write(ignore_cil_template %
+                    ('\n    '.join(sorted(target_ignored_types))))
     finally:
         logging.info('Deleting temporary dir: {}'.format(temp_dir))
         shutil.rmtree(temp_dir)