diff --git a/packages/SettingsLib/DataStore/src/com/android/settingslib/datastore/BackupRestoreContext.kt b/packages/SettingsLib/DataStore/src/com/android/settingslib/datastore/BackupRestoreContext.kt
index c6d6f77..8fe618d 100644
--- a/packages/SettingsLib/DataStore/src/com/android/settingslib/datastore/BackupRestoreContext.kt
+++ b/packages/SettingsLib/DataStore/src/com/android/settingslib/datastore/BackupRestoreContext.kt
@@ -20,7 +20,6 @@
 import android.app.backup.BackupDataOutput
 import android.app.backup.BackupHelper
 import android.os.Build
-import android.os.ParcelFileDescriptor
 import androidx.annotation.RequiresApi
 
 /**
@@ -31,23 +30,8 @@
  */
 class BackupContext
 internal constructor(
-    /**
-     * An open, read-only file descriptor pointing to the last backup state provided by the
-     * application. May be null, in which case no prior state is being provided and the application
-     * should perform a full backup.
-     *
-     * TODO: the state should support marshall/unmarshall for incremental back up.
-     */
-    val oldState: ParcelFileDescriptor?,
-
     /** An open, read/write BackupDataOutput pointing to the backup data destination. */
     private val data: BackupDataOutput,
-
-    /**
-     * An open, read/write file descriptor pointing to an empty file. The application should record
-     * the final backup.
-     */
-    val newState: ParcelFileDescriptor,
 ) {
     /**
      * The quota in bytes for the application's current backup operation.
@@ -68,5 +52,9 @@
         @RequiresApi(Build.VERSION_CODES.P) get() = data.transportFlags
 }
 
-/** Context for restore. */
-class RestoreContext(val key: String)
+/**
+ * Context for restore.
+ *
+ * @param key Entity key
+ */
+class RestoreContext internal constructor(val key: String)
diff --git a/packages/SettingsLib/DataStore/src/com/android/settingslib/datastore/BackupRestoreFileArchiver.kt b/packages/SettingsLib/DataStore/src/com/android/settingslib/datastore/BackupRestoreFileArchiver.kt
index 3db46509..621a8d7 100644
--- a/packages/SettingsLib/DataStore/src/com/android/settingslib/datastore/BackupRestoreFileArchiver.kt
+++ b/packages/SettingsLib/DataStore/src/com/android/settingslib/datastore/BackupRestoreFileArchiver.kt
@@ -18,11 +18,11 @@
 
 import android.app.backup.BackupDataInputStream
 import android.content.Context
-import android.os.ParcelFileDescriptor
 import android.util.Log
 import java.io.File
 import java.io.InputStream
 import java.io.OutputStream
+import java.util.zip.CheckedInputStream
 
 /**
  * File archiver to handle backup and restore for all the [BackupRestoreFileStorage] subclasses.
@@ -62,8 +62,10 @@
             }
         Log.i(LOG_TAG, "[$name] Restore ${data.size()} bytes for $key to $file")
         val inputStream = LimitedNoCloseInputStream(data)
+        checksum.reset()
+        val checkedInputStream = CheckedInputStream(inputStream, checksum)
         try {
-            val codec = BackupCodec.fromId(inputStream.read().toByte())
+            val codec = BackupCodec.fromId(checkedInputStream.read().toByte())
             if (fileStorage != null && fileStorage.defaultCodec().id != codec.id) {
                 Log.i(
                     LOG_TAG,
@@ -71,17 +73,19 @@
                 )
             }
             file.parentFile?.mkdirs() // ensure parent folders are created
-            val wrappedInputStream = codec.decode(inputStream)
+            val wrappedInputStream = codec.decode(checkedInputStream)
             val bytesCopied = file.outputStream().use { wrappedInputStream.copyTo(it) }
             Log.i(LOG_TAG, "[$name] $key restore $bytesCopied bytes with ${codec.name}")
             fileStorage?.onRestoreFinished(file)
+            entityStates[key] = checksum.value
         } catch (e: Exception) {
             Log.e(LOG_TAG, "[$name] Fail to restore $key", e)
         }
     }
 
-    override fun writeNewStateDescription(newState: ParcelFileDescriptor) =
-        fileStorages.forEach { it.writeNewStateDescription(newState) }
+    override fun onRestoreFinished() {
+        fileStorages.forEach { it.onRestoreFinished() }
+    }
 }
 
 private fun BackupRestoreFileStorage.toBackupRestoreEntity() =
diff --git a/packages/SettingsLib/DataStore/src/com/android/settingslib/datastore/BackupRestoreStorage.kt b/packages/SettingsLib/DataStore/src/com/android/settingslib/datastore/BackupRestoreStorage.kt
index 8ff4bc8..ea2fb72 100644
--- a/packages/SettingsLib/DataStore/src/com/android/settingslib/datastore/BackupRestoreStorage.kt
+++ b/packages/SettingsLib/DataStore/src/com/android/settingslib/datastore/BackupRestoreStorage.kt
@@ -22,11 +22,20 @@
 import android.app.backup.BackupHelper
 import android.os.ParcelFileDescriptor
 import android.util.Log
+import androidx.collection.MutableScatterMap
 import com.google.common.io.ByteStreams
 import java.io.ByteArrayOutputStream
+import java.io.DataInputStream
+import java.io.DataOutputStream
+import java.io.EOFException
+import java.io.FileInputStream
+import java.io.FileOutputStream
 import java.io.FilterInputStream
 import java.io.InputStream
 import java.io.OutputStream
+import java.util.zip.CRC32
+import java.util.zip.CheckedInputStream
+import java.util.zip.CheckedOutputStream
 
 internal const val LOG_TAG = "BackupRestoreStorage"
 
@@ -47,6 +56,20 @@
 
     private val entities: List<BackupRestoreEntity> by lazy { createBackupRestoreEntities() }
 
+    /**
+     * Checksum of the data.
+     *
+     * Always call [java.util.zip.Checksum.reset] before using it.
+     */
+    protected val checksum = CRC32()
+
+    /**
+     * Entity states represented by checksum.
+     *
+     * Map key is the entity key, map value is the checksum of backup data.
+     */
+    protected val entityStates = MutableScatterMap<String, Long>()
+
     /** Entities to back up and restore. */
     abstract fun createBackupRestoreEntities(): List<BackupRestoreEntity>
 
@@ -58,7 +81,8 @@
         data: BackupDataOutput,
         newState: ParcelFileDescriptor,
     ) {
-        val backupContext = BackupContext(oldState, data, newState)
+        oldState.readEntityStates(entityStates)
+        val backupContext = BackupContext(data)
         if (!enableBackup(backupContext)) {
             Log.i(LOG_TAG, "[$name] Backup disabled")
             return
@@ -67,34 +91,50 @@
         for (entity in entities) {
             val key = entity.key
             val outputStream = ByteArrayOutputStream()
+            checksum.reset()
+            val checkedOutputStream = CheckedOutputStream(outputStream, checksum)
             val codec = entity.codec() ?: defaultCodec()
             val result =
                 try {
-                    entity.backup(backupContext, wrapBackupOutputStream(codec, outputStream))
+                    entity.backup(backupContext, wrapBackupOutputStream(codec, checkedOutputStream))
                 } catch (exception: Exception) {
                     Log.e(LOG_TAG, "[$name] Fail to backup entity $key", exception)
                     continue
                 }
             when (result) {
                 EntityBackupResult.UPDATE -> {
-                    val payload = outputStream.toByteArray()
-                    val size = payload.size
-                    data.writeEntityHeader(key, size)
-                    data.writeEntityData(payload, size)
-                    Log.i(LOG_TAG, "[$name] Backup entity $key: $size bytes")
+                    if (updateEntityState(key)) {
+                        val payload = outputStream.toByteArray()
+                        val size = payload.size
+                        data.writeEntityHeader(key, size)
+                        data.writeEntityData(payload, size)
+                        Log.i(LOG_TAG, "[$name] Backup entity $key: $size bytes")
+                    } else {
+                        Log.i(
+                            LOG_TAG,
+                            "[$name] Backup entity $key unchanged: ${outputStream.size()} bytes"
+                        )
+                    }
                 }
                 EntityBackupResult.INTACT -> {
                     Log.i(LOG_TAG, "[$name] Backup entity $key intact")
                 }
                 EntityBackupResult.DELETE -> {
+                    entityStates.remove(key)
                     data.writeEntityHeader(key, -1)
                     Log.i(LOG_TAG, "[$name] Backup entity $key deleted")
                 }
             }
         }
+        newState.writeEntityStates(entityStates)
         Log.i(LOG_TAG, "[$name] Backup end")
     }
 
+    private fun updateEntityState(key: String): Boolean {
+        val value = checksum.value
+        return entityStates.put(key, value) != value
+    }
+
     /** Returns if backup is enabled. */
     open fun enableBackup(backupContext: BackupContext): Boolean = true
 
@@ -118,11 +158,12 @@
         Log.i(LOG_TAG, "[$name] Restore $key: ${data.size()} bytes")
         val restoreContext = RestoreContext(key)
         val codec = entity.codec() ?: defaultCodec()
+        val inputStream = LimitedNoCloseInputStream(data)
+        checksum.reset()
+        val checkedInputStream = CheckedInputStream(inputStream, checksum)
         try {
-            entity.restore(
-                restoreContext,
-                wrapRestoreInputStream(codec, LimitedNoCloseInputStream(data))
-            )
+            entity.restore(restoreContext, wrapRestoreInputStream(codec, checkedInputStream))
+            entityStates[key] = checksum.value
         } catch (exception: Exception) {
             Log.e(LOG_TAG, "[$name] Fail to restore entity $key", exception)
         }
@@ -143,7 +184,64 @@
         return BackupCodec.fromId(id.toByte()).decode(inputStream)
     }
 
-    override fun writeNewStateDescription(newState: ParcelFileDescriptor) {}
+    final override fun writeNewStateDescription(newState: ParcelFileDescriptor) {
+        newState.writeEntityStates(entityStates)
+        onRestoreFinished()
+    }
+
+    /** Callbacks when restore finished. */
+    open fun onRestoreFinished() {}
+
+    private fun ParcelFileDescriptor?.readEntityStates(state: MutableScatterMap<String, Long>) {
+        state.clear()
+        if (this == null) return
+        // do not close the streams
+        val fileInputStream = FileInputStream(fileDescriptor)
+        val dataInputStream = DataInputStream(fileInputStream)
+        try {
+            val version = dataInputStream.readByte()
+            if (version != STATE_VERSION) {
+                Log.w(
+                    LOG_TAG,
+                    "[$name] Unexpected state version, read:$version, expected:$STATE_VERSION"
+                )
+                return
+            }
+            var count = dataInputStream.readInt()
+            while (count-- > 0) {
+                val key = dataInputStream.readUTF()
+                val checksum = dataInputStream.readLong()
+                state[key] = checksum
+            }
+        } catch (exception: Exception) {
+            if (exception is EOFException) {
+                Log.d(LOG_TAG, "[$name] Hit EOF when read state file")
+            } else {
+                Log.e(LOG_TAG, "[$name] Fail to read state file", exception)
+            }
+            state.clear()
+        }
+    }
+
+    private fun ParcelFileDescriptor.writeEntityStates(state: MutableScatterMap<String, Long>) {
+        // do not close the streams
+        val fileOutputStream = FileOutputStream(fileDescriptor)
+        val dataOutputStream = DataOutputStream(fileOutputStream)
+        try {
+            dataOutputStream.writeByte(STATE_VERSION.toInt())
+            dataOutputStream.writeInt(state.size)
+            state.forEach { key, value ->
+                dataOutputStream.writeUTF(key)
+                dataOutputStream.writeLong(value)
+            }
+        } catch (exception: Exception) {
+            Log.e(LOG_TAG, "[$name] Fail to write state file", exception)
+        }
+    }
+
+    companion object {
+        private const val STATE_VERSION: Byte = 0
+    }
 }
 
 /**